提交情况：
代码：
#include <iostream> #include <string.h> using namespace std; #define Max 505 #define INF 0x3f3f3f3f typedef struct Node { int length; int cost; }Node; Node Graph[Max][Max]; int n,m,s,d; //分别代表城市个数，高速公路数，开始城市，目的城市 //dist[i]代表从开始城市s到城市i的最短距离，cost[i]则代表从开始城市到城市i的最小花费 int visit[Max],dist[Max],cost[Max],path[Max]; void printPath( int path[] ) //打印路径 { int a = d; int num[Max],top = -1; while ( path[a] != -1 ) { num[++top] = path[a]; a = path[a]; } for( int i=top;i>=0;--i ) cout<<num[i]<<" "; cout<<d<<" "; } void Dijkstra( int start ) { visit[start] = 1; for( int i=0;i<n;++i ) { int vertex = -1,min = INF; for( int j=0;j<n;++j ) //找到最小边，并以该边为中介节点，检查剩余的节点 { if( visit[j] == 0 && dist[j] < min ) { vertex = j; min = dist[j]; } } visit[vertex] = 1; if( vertex == -1 ) return ; for( int j=0;j<n;++j ) { if( visit[j] == 0 && dist[vertex] + Graph[vertex][j].length < dist[j] ) //找到更短的路径 { dist[j] = dist[vertex] + Graph[vertex][j].length; //存储该路径的值 cost[j] = cost[vertex] + Graph[vertex][j].cost; //无条件更新花费 path[j] = vertex; //记录前驱节点 } else if( visit[j] == 0 && dist[vertex] + Graph[vertex][j].length == dist[j] ) { //距离相等，则比较花费 if( cost[vertex] + Graph[vertex][j].cost < cost[j] ) //如果花费更少，则更新花费 { cost[j] = cost[vertex] + Graph[vertex][j].cost; path[j] = vertex; } } } } } int main () { cin>>n>>m>>s>>d; for( int i=0;i<n;++i ) { memset(Graph[i],INF,sizeof(Graph[i])); //自身到自身（即i到i）的距离设为0，话费设为0 Graph[i][i].length = 0; Graph[i][i].cost = 0; } //输入城市之间的距离与长度 for( int i=0;i<m;++i ) { int c1,c2; cin>>c1>>c2; cin>>Graph[c1][c2].length>>Graph[c1][c2].cost; Graph[c2][c1].length = Graph[c1][c2].length; Graph[c2][c1].cost = Graph[c1][c2].cost; } //调用Dijkstra前的初始化， for( int i=0;i<n;++i) { //城市i与城市s有路（即右边相连） if( Graph[s][i].length != INF ) { dist[i] = Graph[s][i].length; cost[i] = Graph[s][i].cost; path[i] = s; } else //没有边相连，则花费和距离都设为无穷大 { dist[i] = INF; cost[i] = INF; path[i] = -1; } } //因为城市自身到自身的长度，花费都为0，所以经过上述初始化操作之后，path[s] = s, //不方便路径输出，再者节点s的前驱节点为s，有点怪。所以将path[s] = -1, //一来没有节点的编号为-1,可以用来在path数组中标记开始节点，当然也不用如此，输出的时候注意一下也可以 path[s] = -1; Dijkstra(s); printPath(path); cout<<dist[d]<<" "<<cost[d]<<endl; return 0; }算法思想： 运用迪杰斯特拉算法，在寻找最短路径时，如果找到更小的路径，则无条件更新该最短路径上的花费，并记录当前节点的前驱节点；如果遇到相同的最短路径，则比较两条路径上的花费，如果当前的最短路径花费更少，则记录下当前最短路径的花费，并记录下当前节点的前驱节点。
