有了一张自驾旅游路线图&＃xff0c;你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序&＃xff0c;帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的&＃xff0c;那么需要输出最便宜的一条路径。
输入格式:
输入说明&＃xff1a;输入数据的第1行给出4个正整数N、M、S、D&＃xff0c;其中N&＃xff08;2≤N≤500&＃xff09;是城市的个数&＃xff0c;顺便假设城市的编号为0~(N−1)&＃xff1b;M是高速公路的条数&＃xff1b;S是出发地的城市编号&＃xff1b;D是目的地的城市编号。随后的M行中&＃xff0c;每行给出一条高速公路的信息&＃xff0c;分别是&＃xff1a;城市1、城市2、高速公路长度、收费额&＃xff0c;中间用空格分开&＃xff0c;数字均为整数且不超过500。输入保证解的存在。
输出格式:
在一行里输出路径的长度和收费总额&＃xff0c;数字间以空格分隔&＃xff0c;输出结尾不能有多余空格。
输入样例:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
输出样例:
3 40
我的答案
1 #include
2 #include
3 #include
4
5 #define ERROR -1
6 #define false 0
7 #define true 1
8 #define MaxVertexNum 100
9 #define INFINITY 65535
10 typedef int Vertex;
11 typedef int WeightType;
12 typedef char DataType;
13 typedef int bool;
14
15
16 typedef struct ENode *PtrToENode;
17 struct ENode {
18 Vertex V1, V2;
19 WeightType Weight;
20 WeightType Cost;
21 };
22 typedef PtrToENode Edge;
23
24 typedef struct GNode *PtrToGNode;
25 struct GNode {
26 int Nv;
27 int Ne;
28 WeightType G[MaxVertexNum][MaxVertexNum];
29 WeightType C[MaxVertexNum][MaxVertexNum];
30 };
31 typedef PtrToGNode MGraph;
32
33 MGraph CreateGraph(int VertexNum);
34 void InsertEdge(MGraph Graph, Edge E);
35 MGraph BuildGraph(int Nv, int Ne);
36 void PrintGraph(MGraph Graph);
37 Vertex FindMinDist(MGraph Graph, int dist[], int collected[]);
38 bool Dijkstra(MGraph Graph, int dist[], int path[], int cost[], Vertex S);
39 void PrintDist(MGraph Graph, int dist[]);
40 void PrintPath(int path[], int N);
41
42 MGraph CreateGraph(int VertexNum)
43 {
44 Vertex V, W;
45 MGraph Graph;
46
47 Graph &＃61; (MGraph)malloc(sizeof(struct GNode));
48 Graph->Nv &＃61; VertexNum;
49 Graph->Ne &＃61; 0;
50
51 for(V&＃61;0;V
52 for(W&＃61;0;W
53 Graph->G[V][W] &＃61; INFINITY;
54 Graph->C[V][W] &＃61; INFINITY;
55 }
56
57 return Graph;
58 }
59
60 void InsertEdge(MGraph Graph, Edge E)
61 {
62 Graph->G[E->V1][E->V2] &＃61; E->Weight;
63 Graph->G[E->V2][E->V1] &＃61; E->Weight;
64 Graph->C[E->V1][E->V2] &＃61; E->Cost;
65 Graph->C[E->V2][E->V1] &＃61; E->Cost;
66 }
67
68 MGraph BuildGraph(int Nv, int Ne)
69 {
70 MGraph Graph;
71 Edge E;
72 int i;
73
74 // scanf("%d", &Nv);
75 Graph &＃61; CreateGraph(Nv);
76
77 Graph->Ne &＃61; Ne;
78 // scanf("%d", &(Graph->Ne));
79 if(Graph->Ne !&＃61; 0) {
80 E &＃61; (Edge)malloc(sizeof(struct ENode));
81 for(i&＃61;0;i
82 scanf("%d %d %d %d\n", &E->V1, &E->V2, &E->Weight, &E->Cost);
83 InsertEdge(Graph, E);
84 }
85 }
86
87 return Graph;
88 }
89
90 void PrintGraph(MGraph Graph)
91 {
92 Vertex V, W;
93 printf("Graph:\n");
94 for(V&＃61;0;V
95 for(W&＃61;0;W
96 printf("[%5d %5d]\t" , Graph->G[V][W], Graph->C[V][W]);
97 printf("\n");
98 }
99 printf("-----------------------\n");
100 }
101
102 Vertex FindMinDist(MGraph Graph, int dist[], int collected[])
103 {
104 Vertex MinV, V;
105 int MinDist &＃61; INFINITY;
106
107 for(V&＃61;0;V
108 if(collected[V] &＃61;&＃61; false && dist[V]
109 MinDist &＃61; dist[V];
110 MinV &＃61; V;
111 }
112 }
113 if(MinDist < INFINITY)
114 return MinV;
115 else return ERROR;
116 }
117
118 bool Dijkstra(MGraph Graph, int dist[], int path[], int cost[], Vertex S)
119 {
120 int collected[MaxVertexNum];
121 Vertex V, W;
122
123 /* 初始化&＃xff1a;此处默认邻接矩阵中不存在的边用INFINITY表示 */
124 for(V&＃61;0;V
125 dist[V] &＃61; Graph->G[S][V];
126 cost[V] &＃61; Graph->C[S][V];
127 if(dist[V]<INFINITY)
128 path[V] &＃61; S;
129 else
130 path[V] &＃61; -1;
131 collected[V] &＃61; false;
132 }
133 // PrintPath(path, Graph->Nv);
134 /* 先将起点收入集合 */
135 dist[S] &＃61; 0;
136 collected[S] &＃61; true;
137
138 while(1) {
139 /* V &＃61; 未被收录顶点中dist最小者 */
140 V &＃61; FindMinDist(Graph, dist, collected);
141 // printf("[FindMinDist] V:%d\n", V);
142 if(V &＃61;&＃61; ERROR) /* 若这样的V不存在 */
143 break; /* 算法结束 */
144 collected[V] &＃61; true; /* 收录 */
145 for(W&＃61;0;W
146 /* 若W是V的邻接点并且未被收录 */
147 if(collected[W]&＃61;&＃61;false && Graph->G[V][W]<INFINITY) {
148 if(Graph->G[V][W]<0) /* 若有负边 */
149 return false; /* 不能正确解决&＃xff0c;返回错误标记 */
150 /* 若收录V使得dist[W]变小&＃xff08;两点距离比一点距离短&＃xff09; */
151 if(dist[V]&＃43;Graph->G[V][W]<dist[W]) {
152 dist[W] &＃61; dist[V] &＃43; Graph->G[V][W]; /* 更新dist[W] */
153 // printf("[FindMinDist] dist[W(%d)]&＃61;%d\n", W, dist[W]);
154 path[W] &＃61; V; /* 更新S到W的路径 */
155 cost[W] &＃61; cost[V] &＃43; Graph->C[V][W];
156 } else if((dist[V]&＃43;Graph->G[V][W] &＃61;&＃61; dist[W])
157 && (cost[V] &＃43; Graph->C[V][W] < cost[W])) {
158 cost[W] &＃61; cost[V] &＃43; Graph->C[V][W];
159 }
160 }
161 }
162 }
163
164 return true; /* 算法执行完毕&＃xff0c;返回正确标记 */
165 }
166
167 void PrintDist(MGraph Graph, int dist[])
168 {
169 Vertex V;
170 for(V&＃61;0;V
171 printf("%d ", dist[V]);
172 }
173 printf("\n");
174 }
175
176 void PrintPath(int path[], int N)
177 {
178 int i;
179 printf("[Path] ");
180 for(i&＃61;0;i
181 printf("%d ",path[i]);
182 printf("\n");
183 }
184
185 int main()
186 {
187 int N, M;
188 Vertex S, D;
189 int *dist, *path, *cost;
190 MGraph Graph;
191 scanf("%d %d %d %d\n", &N, &M, &S, &D);
192 dist &＃61; (int *)malloc(sizeof(int)*N);
193 path &＃61; (int *)malloc(sizeof(int)*N);
194 cost &＃61; (int *)malloc(sizeof(int)*N);
195 Graph &＃61; BuildGraph(N, M);
196 // PrintGraph(Graph);
197 Dijkstra(Graph, dist, path, cost, S);
198 // PrintPath(path, N);
199 printf("%d %d\n", dist[D], cost[D]);
200 return 0;
201 }
京公网安备 11010802041100号