首页 > 其他分享 >07-图5 Saving James Bond - Hard Version（C）

07-图5 Saving James Bond - Hard Version（C）

时间：2024-08-25 22:22:34浏览次数：8  
标签：Saving 07 int James path dist Array data struct

 哈哈，我是真的服了，写了好几天结果给我个这，气死我了，果然还有很大的进步空间。如果有c测试点4，就好了。 又写了一天，是真解决不了了，这个问题等我明白一定来解答

哈哈，

测试点提示内存(KB)用时(ms)结果得分
0sample1 多条最短路，同一点有多路，最近点无路，多连通1841

答案正确

15 / 15
1sample 2 聚集型，均离岸远3641

答案正确

3 / 3
2分散型，均跳不到，有在角上3561

答案正确

2 / 2
3有一只在岸上，有一只在岛上，不能算在内3162

答案正确

3 / 3
4最大N，sample1的复杂版，可选路径8条，后面要更新前面的最短路3082

答案错误

0 / 6
5最小N，一步跳到岸3002

答案正确

1 / 1
题目大致信息。

This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world's most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape -- he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head... Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).

Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him a shortest path to reach one of the banks. The length of a path is the number of jumps that James has to make.

Input Specification:

Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.

Output Specification:

For each test case, if James can escape, output in one line the minimum number of jumps he must make. Then starting from the next line, output the position (x,y) of each crocodile on the path, each pair in one line, from the island to the bank. If it is impossible for James to escape that way, simply give him 0 as the number of jumps. If there are many shortest paths, just output the one with the minimum first jump, which is guaranteed to be unique.

Sample Input 1:

17 15
10 -21
10 21
-40 10
30 -50
20 40
35 10
0 -10
-25 22
40 -40
-30 30
-10 22
0 11
25 21
25 10
10 10
10 35
-30 10

Sample Output 1:

4
0 11
10 21
10 35

Sample Input 2:

4 13
-12 12
12 12
-12 -12
12 -12

Sample Output 2:

0

虽然我不是满分，问题也暂时解决不了，但不妨碍他是一个较好的代码，可以看一下，开头的运行速度，哈哈。毕竟我们相遇必定是为了学习数据结构而来，所以加油。

我的代码主要分为4各部分

首先我先展示头文件，与主函数

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>

int main()
{
	LGraph M;
	Point *Array;
	bool *Visited;
	M = Init_Graph();
	Array = Read_Point_Array(M ->N);
	Visited = (bool*)calloc(M ->N + 1, sizeof(bool));
	M = Build_Graph(M, Array, Visited);
	if(M){
		double *dist;
		int *path;
		int Node;
		Stack S;
		dist = (double*)malloc(sizeof(double) * (M ->N + 1));
		path = (int*)malloc(sizeof(int) * (M ->N + 1));
		Dijkstra(M, dist, path);
		Node = Fllush_Mindata(M, Visited, dist, path);
		S = Init_Stack();
		Push_path_data(S, path, Node);
		Print_Path(S, Array);
	}	
	return 0;
}

第一部分，构造图并插入数据

const double INFITY = 500000.0;

typedef struct Coordinate *Point;
struct Coordinate{
	int X;
	int Y;
};

typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
struct ENode{
	int V1, V2;
	double dist;	
};

typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
	int V;
	double dist;
	PtrToAdjVNode Next;	
};

typedef struct VNode **AdjList;
struct VNode{
	PtrToAdjVNode FirstEdge;	
};

typedef struct GNode *LGraph;
struct GNode{
	int N;
	double D;
	AdjList G;
};


LGraph Build_Graph(LGraph M, Point *Array, bool *Visited);
LGraph Init_Graph();
Point* Read_Point_Array(int N);
bool Up_ashore(Point P, double D);
double Dict_E(Point start, Point end, double D);
void Insert_Graph(LGraph M, Edge E);
LGraph Init_Graph()
{
	LGraph M;
	M = (LGraph)malloc(sizeof(struct GNode));
	scanf("%d %lf", &M ->N, &M ->D);
	M ->G = (AdjList)malloc(sizeof(struct VNode) * (M ->N + 1));
	for(int i = 0; i <= M ->N; i++){
		M ->G[i] = (struct VNode*)malloc(sizeof(struct VNode));
		M ->G[i] ->FirstEdge = NULL;
	}
	return M;
}

Point* Read_Point_Array(int N)
{
	Point *Array;
	Array = (Point*)malloc(sizeof(Point) * (N + 1));
	Array[0] = (Point)malloc(sizeof(struct Coordinate));
	Array[0] ->X = 0;
	Array[0] ->Y = 0;
	for(int i = 1; i <= N; i++){
		Array[i] = (Point)malloc(sizeof(struct Coordinate));
		scanf("%d %d", &(Array[i] ->X), &(Array[i] ->Y));
	}
	return Array;
}

LGraph Build_Graph(LGraph M, Point *Array, bool *Visited)
{
	Edge E;
	bool Up = false;
	bool Up_D = false;
	E = (Edge)malloc(sizeof(struct ENode));
	if(Up_ashore(Array[0], M ->D + 7.5)){
		printf("1\n");
		return NULL;
	}
	for(int i = 1; i <= M ->N; i++){
		if(Up_ashore(Array[i], M ->D + 7.5)){
			Visited[i] = true;
			Up = true;
		}
		E ->dist = Dict_E(Array[0], Array[i], M ->D + 7.5);
		E ->V1 = 0;
		E ->V2 = i;
		if(E ->dist != 0 && E ->dist > 7.5){
			Up_D = true;
			Insert_Graph(M, E);
		}
	}
	if(!Up || !Up_D){
		printf("0\n");
		return NULL;
	}
	
	for(int i = 1; i <= M ->N; i++){
		for(int j = i + 1; j <= M ->N; j++){
			E ->dist = Dict_E(Array[i], Array[j], M ->D);
			E ->V1 = i;
			E ->V2 = j;
			if(E ->dist != 0){
				Insert_Graph(M, E);
			}
		}	
	}
	return M;
}

void Insert_Graph(LGraph M, Edge E)
{
	PtrToAdjVNode NewNode;
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode ->V = E ->V2;
	NewNode ->dist = E ->dist;
	NewNode ->Next = M ->G[E ->V1] ->FirstEdge;
	M ->G[E ->V1] ->FirstEdge = NewNode;
	
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode ->V = E ->V1;
	NewNode ->dist = E ->dist;
	NewNode ->Next = M ->G[E ->V2] ->FirstEdge;
	M ->G[E ->V2] ->FirstEdge = NewNode;
}
double Dict_E(Point start, Point end, double D)
{
	double dis;
	dis = sqrt(pow(start ->X - end ->X, 2) + pow(start ->Y - end ->Y, 2));
	if(dis <= D){
		return dis;
	}else{
		return 0;
	}
}
bool Up_ashore(Point P, double D)
{
	return (abs(P ->X) >= 50 - D || abs(P ->Y) >= 50 - D);
}

第二部分，构建堆

typedef struct HeapNode *HN;
struct HeapNode{
	int sign;
	double dist;
};

typedef struct Heap *MinHeap;
struct Heap{
	HN data;
	int Size;
};

MinHeap Init_dist(LGraph M);
void Insert_Heap(MinHeap H, double Data, int sign);
struct HeapNode Delete_Heap(MinHeap H);
void Creat_Heap(int head, LGraph M, MinHeap H, bool *collected);

void Creat_Heap(int head, LGraph M, MinHeap H, bool *collected)
{
	PtrToAdjVNode G;
	for(G = M ->G[head] ->FirstEdge; G; G = G ->Next){
		if(!collected[G ->V]){
			Insert_Heap(H, G ->dist, G ->V);
		}
	}
}

void Insert_Graph(LGraph M, Edge E)
{
	PtrToAdjVNode NewNode;
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode ->V = E ->V2;
	NewNode ->dist = E ->dist;
	NewNode ->Next = M ->G[E ->V1] ->FirstEdge;
	M ->G[E ->V1] ->FirstEdge = NewNode;
	
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode ->V = E ->V1;
	NewNode ->dist = E ->dist;
	NewNode ->Next = M ->G[E ->V2] ->FirstEdge;
	M ->G[E ->V2] ->FirstEdge = NewNode;
}

MinHeap Init_dist(LGraph M)
{
	MinHeap dist;
	dist = (MinHeap)malloc(sizeof(struct Heap) * (M ->N + 1));
	dist->data = (HN)malloc(sizeof(struct HeapNode) * (M ->N + 1));
	dist ->Size = 0;
	dist ->data[0].sign = -1;
	dist ->data[0].dist = -1;
	return dist;
}
void Insert_Heap(MinHeap H, double Data, int sign)
{
	int i;
	i = ++(H ->Size);
	for(; Data < H ->data[i/2].dist; i /= 2){
		H ->data[i].dist = H ->data[i/2].dist;
		H ->data[i].sign = H ->data[i/2].sign;
	}
	H ->data[i].dist = Data;
	H ->data[i].sign = sign;
}
struct HeapNode Delete_Heap(MinHeap H)
{
	int Child, Parent;
	struct HeapNode Min, Temp;
	if(H ->Size == 0){
		return H ->data[0];
	}
	Min = H ->data[1];
	Temp = H ->data[H ->Size --];
	for(Parent = 1; Parent * 2 <= H ->Size; Parent = Child){
		Child = Parent * 2;
		if((Child != H ->Size) && H ->data[Child].dist > H ->data[Child + 1].dist){
			Child++;
		}
		if(Temp.dist <= H ->data[Child].dist){
			break;
		}else{
			H ->data[Parent].dist = H ->data[Child].dist;
			H ->data[Parent].sign = H ->data[Child].sign;
		}	
	}
	H ->data[Parent].dist = Temp.dist;
	H ->data[Parent].sign = Temp.sign;
	return Min;
}

第三部分，Dijkstra算法，与寻求路径

void Dijkstra(LGraph M, double *dist, int *path)
{
	MinHeap H;
	struct HeapNode HNode;
	bool *collected;
	PtrToAdjVNode G;
	H = Init_dist(M);
	collected = (bool*)malloc(sizeof(bool) * (M ->N + 1));
	Init_DP(dist, path, M ->N);
	for(int i = 0; i <= M ->N; i++){
		Creat_Heap(i, M, H, collected);
		collected[i] = true;
		while(HNode = Delete_Heap(H), HNode.sign != -1){
			collected[HNode.sign] = true;
			if(dist[HNode.sign] > HNode.dist){
				dist[HNode.sign] = HNode.dist;
				path[HNode.sign] = i;
			}
			for(G = M ->G[HNode.sign] ->FirstEdge; G; G = G ->Next){
				if(!collected[G ->V] && dist[G ->V] > dist[HNode.sign] + G ->dist){
					dist[G ->V] = dist[HNode.sign] +  G ->dist;
					path[G ->V] = HNode.sign;
				}
			}
		}	
	}
}

void Init_DP(double *dist, int *path, int N)
{
	for(int i = 0; i <= N; i++)
	{
		dist[i] = INFITY;
		path[i] = -1;
	}
}

第四部分，求取最小路径，巧用堆栈

typedef struct Node *Stack;
struct Node{
	int data;
	Stack Next;
};

bool Find_Root(int *path, int N);
int Fllush_Mindata(LGraph M, bool *Visited, double *dist, int *path);
Stack Init_Stack();
void Push_Stack(Stack S, int data);
int Pop_Stack(Stack S);
bool IsEmpty(Stack S);
void Push_path_data(Stack S,  int *path, int Node);
void Print_Path(Stack S, Point *Array);

void Print_Path(Stack S, Point *Array)
{
	int Node;
	printf("%d\n", S ->data);
	while(!IsEmpty(S)){
		Node = Pop_Stack(S);
		printf("%d %d\n", Array[Node] ->X, Array[Node] ->Y);
	}
}
void Push_path_data(Stack S,  int *path, int Node)
{
	if(Node == 0){
		return ;
	}
	if(Node != 0){
		Push_Stack(S, Node);
		S ->data++;
	}
	Push_path_data(S, path, path[Node]);
}
int Fllush_Mindata(LGraph M, bool *Visited, double *dist, int *path)
{
	int N, Node;
	int Cycle;
	int MinCycle = (int)INFITY;
	double dmin = INFITY;
	for(int i = 1; i <= M ->N; i++){
		Cycle = 0;
		if(Visited[i] && Find_Root(path, i)){
			N = path[i];
			while(N != 0){
				dist[i] += dist[N];
				N = path[N];
				Cycle++;
			}
			if(Cycle == MinCycle){
				if(dist[i] < dmin){
					Node = i;
				}
			}
			if(Cycle < MinCycle){
				dmin = dist[i];
				MinCycle = Cycle;
				Node = i;	
			}
		}
	}
	return Node;
}
bool Find_Root(int *path, int N)
{
	if(N == 0){
		return true;
	}
	if(N == -1){
		return  false;
	}
	return Find_Root(path, path[N]);
}


Stack Init_Stack()
{
	Stack S;
	S = (Stack)malloc(sizeof(struct Node));
	S ->data = 1;
	S ->Next = NULL;
	return S;
}
void Push_Stack(Stack S, int data)
{
	Stack T;
	T = (Stack)malloc(sizeof(struct Node));
	T ->data = data;
	T ->Next = S ->Next;
	S ->Next = T;
}
int Pop_Stack(Stack S)
{
	int temp;
	Stack Top;
	if(IsEmpty(S)){
		printf("IS Empty the Stack!\n");
		return -1;
	}else{
		Top = S ->Next;
		S ->Next = Top ->Next;
		temp = Top ->data;
		free(Top);
		return temp;
	}
}
bool IsEmpty(Stack S)
{
	return (S->Next == NULL);
}

我的全部AC：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>

const double INFITY = 500000.0;

typedef struct Coordinate *Point;
struct Coordinate{
	int X;
	int Y;
};

typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
struct ENode{
	int V1, V2;
	double dist;	
};

typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
	int V;
	double dist;
	PtrToAdjVNode Next;	
};

typedef struct VNode **AdjList;
struct VNode{
	PtrToAdjVNode FirstEdge;	
};

typedef struct GNode *LGraph;
struct GNode{
	int N;
	double D;
	AdjList G;
};

typedef struct HeapNode *HN;
struct HeapNode{
	int sign;
	double dist;
};

typedef struct Heap *MinHeap;
struct Heap{
	HN data;
	int Size;
};

typedef struct Node *Stack;
struct Node{
	int data;
	Stack Next;
};

LGraph Build_Graph(LGraph M, Point *Array, bool *Visited);
LGraph Init_Graph();
Point* Read_Point_Array(int N);
bool Up_ashore(Point P, double D);
double Dict_E(Point start, Point end, double D);
void Insert_Graph(LGraph M, Edge E);
MinHeap Init_dist(LGraph M);
void Insert_Heap(MinHeap H, double Data, int sign);
struct HeapNode Delete_Heap(MinHeap H);
void Creat_Heap(int head, LGraph M, MinHeap H, bool *collected);
void Init_DP(double *dist, int *path, int N);
void Dijkstra(LGraph M, double *dist, int *path);
bool Find_Root(int *path, int N);
int Fllush_Mindata(LGraph M, bool *Visited, double *dist, int *path);
Stack Init_Stack();
void Push_Stack(Stack S, int data);
int Pop_Stack(Stack S);
bool IsEmpty(Stack S);
void Push_path_data(Stack S,  int *path, int Node);
void Print_Path(Stack S, Point *Array);

int main()
{
	LGraph M;
	Point *Array;
	bool *Visited;
	M = Init_Graph();
	Array = Read_Point_Array(M ->N);
	Visited = (bool*)calloc(M ->N + 1, sizeof(bool));
	M = Build_Graph(M, Array, Visited);
	if(M){
		double *dist;
		int *path;
		int Node;
		Stack S;
		dist = (double*)malloc(sizeof(double) * (M ->N + 1));
		path = (int*)malloc(sizeof(int) * (M ->N + 1));
		Dijkstra(M, dist, path);
		Node = Fllush_Mindata(M, Visited, dist, path);
		S = Init_Stack();
		Push_path_data(S, path, Node);
		Print_Path(S, Array);
	}	
	return 0;
}
void Print_Path(Stack S, Point *Array)
{
	int Node;
	printf("%d\n", S ->data);
	while(!IsEmpty(S)){
		Node = Pop_Stack(S);
		printf("%d %d\n", Array[Node] ->X, Array[Node] ->Y);
	}
}
void Push_path_data(Stack S,  int *path, int Node)
{
	if(Node == 0){
		return ;
	}
	if(Node != 0){
		Push_Stack(S, Node);
		S ->data++;
	}
	Push_path_data(S, path, path[Node]);
}
int Fllush_Mindata(LGraph M, bool *Visited, double *dist, int *path)
{
	int N, Node;
	int Cycle;
	int MinCycle = (int)INFITY;
	double dmin = INFITY;
	for(int i = 1; i <= M ->N; i++){
		Cycle = 0;
		if(Visited[i] && Find_Root(path, i)){
			N = path[i];
			while(N != 0){
				dist[i] += dist[N];
				N = path[N];
				Cycle++;
			}
			if(Cycle == MinCycle){
				if(dist[i] < dmin){
					Node = i;
				}
			}
			if(Cycle < MinCycle){
				dmin = dist[i];
				MinCycle = Cycle;
				Node = i;	
			}
		}
	}
	return Node;
}
bool Find_Root(int *path, int N)
{
	if(N == 0){
		return true;
	}
	if(N == -1){
		return  false;
	}
	return Find_Root(path, path[N]);
}
LGraph Build_Graph(LGraph M, Point *Array, bool *Visited)
{
	Edge E;
	bool Up = false;
	bool Up_D = false;
	E = (Edge)malloc(sizeof(struct ENode));
	if(Up_ashore(Array[0], M ->D + 7.5)){
		printf("1\n");
		return NULL;
	}
	for(int i = 1; i <= M ->N; i++){
		if(Up_ashore(Array[i], M ->D + 7.5)){
			Visited[i] = true;
			Up = true;
		}
		E ->dist = Dict_E(Array[0], Array[i], M ->D + 7.5);
		E ->V1 = 0;
		E ->V2 = i;
		if(E ->dist != 0 && E ->dist > 7.5){
			Up_D = true;
			Insert_Graph(M, E);
		}
	}
	if(!Up || !Up_D){
		printf("0\n");
		return NULL;
	}
	
	for(int i = 1; i <= M ->N; i++){
		for(int j = i + 1; j <= M ->N; j++){
			E ->dist = Dict_E(Array[i], Array[j], M ->D);
			E ->V1 = i;
			E ->V2 = j;
			if(E ->dist != 0){
				Insert_Graph(M, E);
			}
		}	
	}
	return M;
}
void Dijkstra(LGraph M, double *dist, int *path)
{
	MinHeap H;
	struct HeapNode HNode;
	bool *collected;
	PtrToAdjVNode G;
	H = Init_dist(M);
	collected = (bool*)malloc(sizeof(bool) * (M ->N + 1));
	Init_DP(dist, path, M ->N);
	for(int i = 0; i <= M ->N; i++){
		Creat_Heap(i, M, H, collected);
		collected[i] = true;
		while(HNode = Delete_Heap(H), HNode.sign != -1){
			collected[HNode.sign] = true;
			if(dist[HNode.sign] > HNode.dist){
				dist[HNode.sign] = HNode.dist;
				path[HNode.sign] = i;
			}
			for(G = M ->G[HNode.sign] ->FirstEdge; G; G = G ->Next){
				if(!collected[G ->V] && dist[G ->V] > dist[HNode.sign] + G ->dist){
					dist[G ->V] = dist[HNode.sign] +  G ->dist;
					path[G ->V] = HNode.sign;
				}
			}
		}	
	}
}

void Init_DP(double *dist, int *path, int N)
{
	for(int i = 0; i <= N; i++)
	{
		dist[i] = INFITY;
		path[i] = -1;
	}
}
void Creat_Heap(int head, LGraph M, MinHeap H, bool *collected)
{
	PtrToAdjVNode G;
	for(G = M ->G[head] ->FirstEdge; G; G = G ->Next){
		if(!collected[G ->V]){
			Insert_Heap(H, G ->dist, G ->V);
		}
	}
}

void Insert_Graph(LGraph M, Edge E)
{
	PtrToAdjVNode NewNode;
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode ->V = E ->V2;
	NewNode ->dist = E ->dist;
	NewNode ->Next = M ->G[E ->V1] ->FirstEdge;
	M ->G[E ->V1] ->FirstEdge = NewNode;
	
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode ->V = E ->V1;
	NewNode ->dist = E ->dist;
	NewNode ->Next = M ->G[E ->V2] ->FirstEdge;
	M ->G[E ->V2] ->FirstEdge = NewNode;
}

LGraph Init_Graph()
{
	LGraph M;
	M = (LGraph)malloc(sizeof(struct GNode));
	scanf("%d %lf", &M ->N, &M ->D);
	M ->G = (AdjList)malloc(sizeof(struct VNode) * (M ->N + 1));
	for(int i = 0; i <= M ->N; i++){
		M ->G[i] = (struct VNode*)malloc(sizeof(struct VNode));
		M ->G[i] ->FirstEdge = NULL;
	}
	return M;
}
Point* Read_Point_Array(int N)
{
	Point *Array;
	Array = (Point*)malloc(sizeof(Point) * (N + 1));
	Array[0] = (Point)malloc(sizeof(struct Coordinate));
	Array[0] ->X = 0;
	Array[0] ->Y = 0;
	for(int i = 1; i <= N; i++){
		Array[i] = (Point)malloc(sizeof(struct Coordinate));
		scanf("%d %d", &(Array[i] ->X), &(Array[i] ->Y));
	}
	return Array;
}
double Dict_E(Point start, Point end, double D)
{
	double dis;
	dis = sqrt(pow(start ->X - end ->X, 2) + pow(start ->Y - end ->Y, 2));
	if(dis <= D){
		return dis;
	}else{
		return 0;
	}
}
bool Up_ashore(Point P, double D)
{
	return (abs(P ->X) >= 50 - D || abs(P ->Y) >= 50 - D);
}


MinHeap Init_dist(LGraph M)
{
	MinHeap dist;
	dist = (MinHeap)malloc(sizeof(struct Heap) * (M ->N + 1));
	dist->data = (HN)malloc(sizeof(struct HeapNode) * (M ->N + 1));
	dist ->Size = 0;
	dist ->data[0].sign = -1;
	dist ->data[0].dist = -1;
	return dist;
}
void Insert_Heap(MinHeap H, double Data, int sign)
{
	int i;
	i = ++(H ->Size);
	for(; Data < H ->data[i/2].dist; i /= 2){
		H ->data[i].dist = H ->data[i/2].dist;
		H ->data[i].sign = H ->data[i/2].sign;
	}
	H ->data[i].dist = Data;
	H ->data[i].sign = sign;
}
struct HeapNode Delete_Heap(MinHeap H)
{
	int Child, Parent;
	struct HeapNode Min, Temp;
	if(H ->Size == 0){
		return H ->data[0];
	}
	Min = H ->data[1];
	Temp = H ->data[H ->Size --];
	for(Parent = 1; Parent * 2 <= H ->Size; Parent = Child){
		Child = Parent * 2;
		if((Child != H ->Size) && H ->data[Child].dist > H ->data[Child + 1].dist){
			Child++;
		}
		if(Temp.dist <= H ->data[Child].dist){
			break;
		}else{
			H ->data[Parent].dist = H ->data[Child].dist;
			H ->data[Parent].sign = H ->data[Child].sign;
		}	
	}
	H ->data[Parent].dist = Temp.dist;
	H ->data[Parent].sign = Temp.sign;
	return Min;
}



Stack Init_Stack()
{
	Stack S;
	S = (Stack)malloc(sizeof(struct Node));
	S ->data = 1;
	S ->Next = NULL;
	return S;
}
void Push_Stack(Stack S, int data)
{
	Stack T;
	T = (Stack)malloc(sizeof(struct Node));
	T ->data = data;
	T ->Next = S ->Next;
	S ->Next = T;
}
int Pop_Stack(Stack S)
{
	int temp;
	Stack Top;
	if(IsEmpty(S)){
		printf("IS Empty the Stack!\n");
		return -1;
	}else{
		Top = S ->Next;
		S ->Next = Top ->Next;
		temp = Top ->data;
		free(Top);
		return temp;
	}
}
bool IsEmpty(Stack S)
{
	return (S->Next == NULL);
}

 下面是我的测试代码，后期我会在刷新数据，参考我上述的全部代码。

主要是，之前为了解决问题搞得测试代码，现在是真服了，我解决不了

Visited[0] = 0
Visited[1] = 0
Visited[2] = 0
Visited[3] = 1
Visited[4] = 1
Visited[5] = 1
Visited[6] = 1
Visited[7] = 0
Visited[8] = 0
Visited[9] = 1
Visited[10] = 1
Visited[11] = 0
Visited[12] = 0
Visited[13] = 0
Visited[14] = 0
Visited[15] = 0
Visited[16] = 1
Visited[17] = 1
15 ->0
== 14.142136
12 ->0
== 11.000000
7 ->0
== 10.000000
7 ->1
== 14.866069
16 ->2
== 14.000000
上岸了!
15 ->2
== 11.000000
13 ->2
== 15.000000
12 ->2
== 14.142136
17 ->3
== 10.000000
上岸了!
9 ->4
== 14.142136
上岸了!
16 ->5
== 11.180340
上岸了!
14 ->6
== 10.000000
13 ->6
== 14.866069
1 ->7
== 14.866069
0 ->7
== 10.000000
17 ->8
== 13.000000
上岸了!
11 ->8
== 15.000000
10 ->8
== 9.433981
上岸了!
4 ->9
== 14.142136
上岸了!
8 ->10
== 9.433981
12 ->11
== 14.866069
8 ->11
== 15.000000
15 ->12
== 10.049876
11 ->12
== 14.866069
2 ->12
== 14.142136
0 ->12
== 11.000000
14 ->13
== 11.000000
6 ->13
== 14.866069
上岸了!
2 ->13
== 15.000000
15 ->14
== 15.000000
13 ->14
== 11.000000
6 ->14
== 10.000000
上岸了!
14 ->15
== 15.000000
12 ->15
== 10.049876
2 ->15
== 11.000000
0 ->15
== 14.142136
5 ->16
== 11.180340
上岸了!
2 ->16
== 14.000000
8 ->17
== 13.000000
3 ->17
== 10.000000
上岸了!
1 -> 7
dist[1] == 24.866069
path[1] == 7
15 -> 12
dist[15] == 21.049876
path[15] == 12
11 -> 12
dist[11] == 25.866069
path[11] == 12
2 -> 12
dist[2] == 25.142136
path[2] == 12
14 -> 15
dist[14] == 29.142136
path[14] == 15




5 -> 16
dist[5] == 25.180340
path[5] == 16
14 -> 13
dist[14] == 26.000000
path[14] == 13
6 -> 13
dist[6] == 29.866069
path[6] == 13


8 -> 17
dist[8] == 23.000000
path[8] == 17



Visited[0] = 0  dist[0] = 500000        path[0] = -1
Visited[1] = 0  dist[1] = 25    path[1] = 7
Visited[2] = 0  dist[2] = 25    path[2] = 12
Visited[3] = 1  dist[3] = 500000        path[3] = -1
Visited[4] = 1  dist[4] = 500000        path[4] = -1
Visited[5] = 1  dist[5] = 25    path[5] = 16
Visited[6] = 1  dist[6] = 30    path[6] = 13
Visited[7] = 0  dist[7] = 10    path[7] = 0
Visited[8] = 0  dist[8] = 23    path[8] = 17
Visited[9] = 1  dist[9] = 14    path[9] = 4
Visited[10] = 1 dist[10] = 9    path[10] = 8
Visited[11] = 0 dist[11] = 15   path[11] = 8
Visited[12] = 0 dist[12] = 11   path[12] = 0
Visited[13] = 0 dist[13] = 15   path[13] = 2
Visited[14] = 0 dist[14] = 10   path[14] = 6
Visited[15] = 0 dist[15] = 14   path[15] = 0
Visited[16] = 1 dist[16] = 14   path[16] = 2
Visited[17] = 1 dist[17] = 10   path[17] = 3
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>

const double INFITY = 500000.0;

typedef struct Coordinate *Point;
struct Coordinate{
	int X;
	int Y;
};

typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
struct ENode{
	int V1, V2;
	double dist;	
};

typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
	int V;
	double dist;
	PtrToAdjVNode Next;	
};

typedef struct VNode **AdjList;
struct VNode{
	PtrToAdjVNode FirstEdge;	
};

typedef struct GNode *LGraph;
struct GNode{
	int N;
	double D;
	AdjList G;
};

typedef struct HeapNode *HN;
struct HeapNode{
	int sign;
	double dist;
};

typedef struct Heap *MinHeap;
struct Heap{
	HN data;
	int Size;
};

typedef struct Node *Stack;
struct Node{
	int data;
	Stack Next;
};

LGraph Build_Graph(LGraph M, Point *Array, bool *Visited);
LGraph Init_Graph();
Point* Read_Point_Array(int N);
bool Up_ashore(Point P, double D);
double Dict_E(Point start, Point end, double D);
void Insert_Graph(LGraph M, Edge E);
MinHeap Init_dist(LGraph M);
void Insert_Heap(MinHeap H, double Data, int sign);
struct HeapNode Delete_Heap(MinHeap H);
void Creat_Heap(int head, LGraph M, MinHeap H, bool *collected);
void Init_DP(double *dist, int *path, int N);
void Dijkstra(LGraph M, double *dist, int *path);
void Print_Check(LGraph M, bool *Visited);

int main()
{
	LGraph M;
	Point *Array;
	bool *Visited;
	M = Init_Graph();
	Array = Read_Point_Array(M ->N);
	Visited = (bool*)calloc(M ->N + 1, sizeof(bool));
	M = Build_Graph(M, Array, Visited);
	for(int i = 0; i <= M ->N; i++){
		printf("Visited[%d] = %d\n", i, Visited[i]);
	}
	Print_Check(M, Visited);
	if(M){
		double *dist;
		int *path;
		dist = (double*)malloc(sizeof(double) * (M ->N + 1));
		path = (int*)malloc(sizeof(int) * (M ->N + 1));
		Dijkstra(M, dist, path);
		for(int i = 0; i <= M ->N; i++){
			printf("Visited[%d] = %d\tdist[%d] = %.lf\tpath[%d] = %d\n", i, Visited[i], i, dist[i], i, path[i]);
		}
	}	
	return 0;
}
LGraph Build_Graph(LGraph M, Point *Array, bool *Visited)
{
	Edge E;
	bool Up = false;
	E = (Edge)malloc(sizeof(struct ENode));
	if(Up_ashore(Array[0], M ->D + 7.5)){
		printf("1\n");
		return NULL;
	}
	for(int i = 1; i <= M ->N; i++){
		if(Up_ashore(Array[i], M ->D + 7.5)){
			Visited[i] = true;
			Up = true;
		}
		E ->dist = Dict_E(Array[0], Array[i], M ->D + 7.5);
		E ->V1 = 0;
		E ->V2 = i;
		if(E ->dist != 0){
			Insert_Graph(M, E);
		}
	}
	
	if(!Up){
		printf("0\n");
		return NULL;
	}
	
	for(int i = 1; i <= M ->N; i++){
		for(int j = i + 1; j <= M ->N; j++){
			E ->dist = Dict_E(Array[i], Array[j], M ->D);
			E ->V1 = i;
			E ->V2 = j;
			if(E ->dist != 0){
				Insert_Graph(M, E);
			}
		}	
	}
	return M;
}
void Dijkstra(LGraph M, double *dist, int *path)
{
	MinHeap H;
	struct HeapNode HNode;
	bool *collected;
	PtrToAdjVNode G;
	H = Init_dist(M);
	collected = (bool*)malloc(sizeof(bool) * (M ->N + 1));
	Init_DP(dist, path, M ->N);
	for(int i = 0; i <= M ->N; i++){
		Creat_Heap(i, M, H, collected);
		collected[i] = true;
		while(HNode = Delete_Heap(H), HNode.sign != -1){
			collected[HNode.sign] = true;
			if(dist[HNode.sign] > HNode.dist){
				dist[HNode.sign] = HNode.dist;
				path[HNode.sign] = i;
			}
			for(G = M ->G[HNode.sign] ->FirstEdge; G; G = G ->Next){
				if(!collected[G ->V] && dist[G ->V] > dist[HNode.sign] + G ->dist){
					dist[G ->V] = dist[HNode.sign] +  G ->dist;
					path[G ->V] = HNode.sign;
					printf("%d -> %d\n", G ->V, HNode.sign);
					printf("dist[%d] == %lf\n", G ->V, dist[G ->V]);
					printf("path[%d] == %d\n", G ->V, path[G ->V]);
				}
			}
		}
		printf("\n\n");
	}
}
void Print_Check(LGraph M, bool *Visited)
{
	PtrToAdjVNode G;
	for(int i = 0; i <= M ->N; i++){
		for(G = M ->G[i] ->FirstEdge; G; G = G ->Next){
			printf("%d ->%d\n", G ->V, i);
			printf("== %lf\n", G ->dist);
			if(Visited[G ->V]){
				printf("上岸了!\n");
			}
		}
	}	
}
void Init_DP(double *dist, int *path, int N)
{
	for(int i = 0; i <= N; i++)
	{
		dist[i] = INFITY;
		path[i] = -1;
	}
}
void Creat_Heap(int head, LGraph M, MinHeap H, bool *collected)
{
	PtrToAdjVNode G;
	for(G = M ->G[head] ->FirstEdge; G; G = G ->Next){
		if(!collected[G ->V]){
			Insert_Heap(H, G ->dist, G ->V);
		}
	}
}

void Insert_Graph(LGraph M, Edge E)
{
	PtrToAdjVNode NewNode;
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode ->V = E ->V2;
	NewNode ->dist = E ->dist;
	NewNode ->Next = M ->G[E ->V1] ->FirstEdge;
	M ->G[E ->V1] ->FirstEdge = NewNode;
	
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode ->V = E ->V1;
	NewNode ->dist = E ->dist;
	NewNode ->Next = M ->G[E ->V2] ->FirstEdge;
	M ->G[E ->V2] ->FirstEdge = NewNode;
}
LGraph Init_Graph()
{
	LGraph M;
	M = (LGraph)malloc(sizeof(struct GNode));
	scanf("%d %lf", &M ->N, &M ->D);
	M ->G = (AdjList)malloc(sizeof(struct VNode) * (M ->N + 1));
	for(int i = 0; i <= M ->N; i++){
		M ->G[i] = (struct VNode*)malloc(sizeof(struct VNode));
		M ->G[i] ->FirstEdge = NULL;
	}
	return M;
}
Point* Read_Point_Array(int N)
{
	Point *Array;
	Array = (Point*)malloc(sizeof(Point) * (N + 1));
	Array[0] = (Point)malloc(sizeof(struct Coordinate));
	Array[0] ->X = 0;
	Array[0] ->Y = 0;
	for(int i = 1; i <= N; i++){
		Array[i] = (Point)malloc(sizeof(struct Coordinate));
		scanf("%d %d", &(Array[i] ->X), &(Array[i] ->Y));
	}
	return Array;
}
double Dict_E(Point start, Point end, double D)
{
	double dis;
	dis = sqrt(pow(start ->X - end ->X, 2) + pow(start ->Y - end ->Y, 2));
	if(dis <= D){
		return dis;
	}else{
		return 0;
	}
}
bool Up_ashore(Point P, double D)
{
	return (abs(P ->X) >= 50 - D || abs(P ->Y) >= 50 - D);
}
MinHeap Init_dist(LGraph M)
{
	MinHeap dist;
	dist = (MinHeap)malloc(sizeof(struct Heap) * (M ->N + 1));
	dist->data = (HN)malloc(sizeof(struct HeapNode) * (M ->N + 1));
	dist ->Size = 0;
	dist ->data[0].sign = -1;
	dist ->data[0].dist = -1;
	return dist;
}
void Insert_Heap(MinHeap H, double Data, int sign)
{
	int i;
	i = ++(H ->Size);
	for(; Data < H ->data[i/2].dist; i /= 2){
		H ->data[i].dist = H ->data[i/2].dist;
		H ->data[i].sign = H ->data[i/2].sign;
	}
	H ->data[i].dist = Data;
	H ->data[i].sign = sign;
}
struct HeapNode Delete_Heap(MinHeap H)
{
	int Child, Parent;
	struct HeapNode Min, Temp;
	int Temp_sign;
	if(H ->Size == 0){
		return H ->data[0];
	}
	Min = H ->data[1];
	Temp = H ->data[H ->Size --];
	for(Parent = 1; Parent * 2 <= H ->Size; Parent = Child){
		Child = Parent * 2;
		if((Child != H ->Size) && H ->data[Child].dist > H ->data[Child + 1].dist){
			Child++;
		}
		if(Temp.dist <= H ->data[Child].dist){
			break;
		}else{
			H ->data[Parent].dist = H ->data[Child].dist;
			H ->data[Parent].sign = H ->data[Child].sign;
		}	
	}
	H ->data[Parent].dist = Temp.dist;
	H ->data[Parent].sign = Temp.sign;
	return Min;
}

标签：Saving,07,int,James,path,dist,Array,data,struct
From： https://blog.csdn.net/2301_80474443/article/details/141507501

相关文章

  • 2038-01-19 11:14:07
    2038年1月19日星期二我走进齐州第〇中学，开始我人生的第4997天。寒风刺骨，我坐在初二（10）班的教室内瑟瑟发抖。上完了语文、英语、物理课，全班来到信息教室。“什么时候能吃饭啊”我在电脑面前想。正在我想的时候，突然2036年8月17日星期日今天我收获了第100个......
  • 《2038-01-19 11:14:07》解读
    说明：本文设定三个李华，以及多个世代，会进行标注。虽然是作者写的，但是本文解读仅供参考（也就是说，你爱解读啥就解读啥）常用数字：1901-12-1404:45:52距离1970-01-0108:00:00\(-2147483648\)秒2038-01-1911:14:07距离1970-01-0108:00:00\(2147483647\)秒0世代2038年1......
  • TMDOG的微服务之路_07——初入微服务，NestJS微服务快速入门
    TMDOG的微服务之路_07——初入微服务，NestJS微服务快速入门博客地址：TMDOG的博客在前几篇博客中，我们探讨了如何在NestJS中的一些基础功能，并可以使用NestJS实现一个简单的单体架构后端应用。本篇博客，我们将进入微服务架构，以一个简单的NestJS示例快速了解微服务架构。1.什......
  • wsl损坏，WSLRegisterDistribution Failed with Error 0x8007019e
    背景之前由于关机中断还是什么原因，导致wsl不能用了，今天心血来潮想要用一下wsl，于是找办法修了一下。过程根据下面这个文章进行修复的。https://thegeekpage.com/wslregisterdistribution-failed-with-error-0x8007019e/我执行了以下操作：关闭linux子系统，重启；开启子系统，重启......
  • 读软件开发安全之道：概念、设计与实施07密码学（上）
    1. 加密工具1.1. 加密工具之所以没有得到充分使用，就是因为人们往往认为密码学是一个准入门槛极高的专业领域1.2. 如今的加密学大部分都源自纯数学，所以只要能够正确使用，加密学确实行之有效1.2.1. 不代表这些算法本身确实无法破解，而是需要数学领域出现重大突破才能实现破解......
  • 1075 链表元素分类——PAT乙级
    给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而[0,K]区间内的元素都排在大于K的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为18→7→-4→0→5→-6→10→11→-2，K为10，则输出应该为-4→-6→-2→7→0→5→10......
  • 微软RDL远程代码执行超高危漏洞（CVE-2024-38077）漏洞检测排查方式
    漏洞名称：微软RDL远程代码执行超高危漏洞（CVE-2024-38077）CVSScore:  9.8漏洞描述：CVE-2024-38077是微软近期披露的一个极其严重的远程代码执行漏洞。该漏洞存在于Windows远程桌面许可管理服务（RDL）中，攻击者无需任何权限即可实现远程代码执行，获取服务器最高权限。由于在解码用......
  • Springboot计算机毕业设计旅游景点综合服务系统30079
    本系统（程序+源码+数据库+调试部署+开发环境）带论文文档1万字以上，文末可获取，系统界面在最后面。系统程序文件列表用户,景点管理,景点信息,订票信息,纪念商品,商品购买,景点分类,商品分类开题报告内容一、选题背景及意义随着旅游业的蓬勃发展，游客对于旅游体验的需求日益多元......
  • LGP10702 [SNCPC2024] 下棋题解
    P10702[SNCPC2024]下棋本蒟蒻的第一篇题解定位博弈论（nim）+进制转换相关知识OIWIKI博弈论NIM进制转换正题读题所有k进制下所有数位的乘积为自身因子的数。他称之为LNC数。给出x枚棋子，然后LNC选定一个整数k(k≥2)。随后他们交替取走若干枚棋子，要求取走的棋......
  • Oseltamivir acid (GS 4071) 是 Oseltamivir phosphate 的活性代谢物 |MedChemExpress
    中文名：奥斯他伟酸CAS：187227-45-8品牌：MedChemExpress(MCE)存储条件：4°C,storedundernitrogen生物活性：Oseltamiviracid(GS4071)是Oseltamivirphosphate的活性代谢物，是一种具有口服生物利用度的强效选择性流感病毒神经氨酸酶抑制剂(IC50=2nM) 对甲型和乙型流......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99