1 #include <cstdio> 2 #include <stdlib.h> 3 const int INFINITY = 65536; 4 const int MaxVertexNum = 501; 5 const int ERROR = -1; 6 int dist[MaxVertexNum], path[MaxVertexNum], collected[MaxVertexNum],fare[MaxVertexNum]; 7 typedef int Vertex; 8 typedef int WeightType; 9 10 typedef struct GNode * MGraph; 11 struct GNode { 12 int Nv; 13 int Ne; 14 WeightType G[MaxVertexNum][MaxVertexNum]; 15 WeightType F[MaxVertexNum][MaxVertexNum]; 16 }; 17 18 19 20 Vertex FindMinDist( MGraph Graph ) 21 { /* 返回未被收录顶点中dist最小者 */ 22 Vertex MinV, V; 23 int MinDist = INFINITY; 24 25 for (V=0; V<Graph->Nv; V++) { 26 if ( collected[V]==false && dist[V]<MinDist) { 27 /* 若V未被收录,且dist[V]更小 */ 28 MinDist = dist[V]; /* 更新最小距离 */ 29 MinV = V; /* 更新对应顶点 */ 30 } 31 } 32 if (MinDist < INFINITY) /* 若找到最小dist */ 33 return MinV; /* 返回对应的顶点下标 */ 34 else return ERROR; /* 若这样的顶点不存在,返回错误标记 */ 35 } 36 37 38 39 void init(MGraph Graph) 40 { 41 Vertex V; 42 for( V=0; V<Graph->Nv; V++) { 43 44 fare[V] = INFINITY; 45 } 46 } 47 48 bool Dijkstra( MGraph Graph, Vertex S ) 49 { 50 51 Vertex V, W; 52 53 /* 初始化:此处默认邻接矩阵中不存在的边用INFINITY表示 */ 54 for ( V=0; V<Graph->Nv; V++ ) { 55 dist[V] = Graph->G[S][V]; 56 fare[V] = Graph->F[S][V]; 57 if ( dist[V]<INFINITY ) 58 path[V] = S; 59 else 60 path[V] = -1; 61 collected[V] = false; 62 } 63 64 /* 先将起点收入集合 */ 65 dist[S] = 0; 66 collected[S] = true; 67 68 while (1) { 69 /* V = 未被收录顶点中dist最小者 */ 70 V = FindMinDist( Graph ); 71 if ( V==ERROR ) /* 若这样的V不存在 */ 72 break; /* 算法结束 */ 73 collected[V] = true; /* 收录V */ 74 for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */ 75 /* 若W是V的邻接点并且未被收录 */ 76 if ( collected[W]==false && Graph->G[V][W]<INFINITY ) { 77 78 if ( Graph->G[V][W]<0 ) /* 若有负边 */ 79 return false; /* 不能正确解决,返回错误标记 */ 80 81 /* 若收录V使得dist[W]变小 */ 82 if ( dist[V]+Graph->G[V][W] < dist[W]) { 83 dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */ 84 path[W] = V; /* 更新S到W的路径 */ 85 fare[W] = fare[V]+Graph->F[V][W]; 86 } 87 else if(dist[V]+Graph->G[V][W] == dist[W] and fare[V] + Graph->F[V][W] < fare[W] ) { 88 path[W] = V; /* 更新S到W的路径 */ 89 fare[W] = fare[V]+Graph->F[V][W]; 90 } 91 } 92 } /* while结束*/ 93 return true; /* 算法执行完毕,返回正确标记 */ 94 } 95 96 97 MGraph buildGraph(int Nv, int Ne) 98 { 99 int S, E, len, fees; 100 101 MGraph Graph = (MGraph) malloc(sizeof(struct GNode)); 102 //init 103 Graph->Nv = Nv; 104 Graph->Ne = Ne; 105 for(int i=0; i<Nv; i++) { 106 for(int j=0; j<Nv; j++) { 107 Graph->G[i][j] = INFINITY; 108 Graph->F[i][j] = INFINITY; 109 } 110 } 111 112 for(int i=0; i<Ne; i++) { 113 scanf("%d %d %d %d", &S, &E, &len, &fees); 114 Graph->G[S][E] = len; 115 Graph->G[E][S] = len; 116 Graph->F[E][S] = fees; 117 Graph->F[S][E] = fees; 118 } 119 return Graph; 120 } 121 122 int main() 123 { 124 int N, M, S, D; 125 scanf("%d%d%d%d", &N, &M, &S, &D); 126 127 MGraph Graph = buildGraph(N, M); 128 129 Dijkstra(Graph, S); 130 131 printf("%d %d\n", dist[D], fare[D]); 132 133 }View Code