本文共 1313 字，大约阅读时间需要 4 分钟。

题目链接：

题目描述：

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:

输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出格式:

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

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

本题考察的是附加额外条件的Dijkstra算法，原始Dijkstra算法中的关键步骤，是判断当新加入的某结点使得当前最短距离变得更小时，要更新最短路径，否则路径不变。本题中的Dijkstra算法还要求考察路径费用的权值，即使新加入的某结点没有使最短距离变得更短，但如果它能产生相同的最短距离、并且费用最小，还是要更新最短路径。只有当经过新结点的路径比当前最短路径长、或者虽然长度相等但是费用没有减少时，才不更新路径。

样例示意图：

参考代码：

#include 
   
    #include 
    
      #define INF 65535int n,m,s,d;int map[501][501];int cost[501][501];int visited[501];int dist[501];void init(){     int i,j;  for(i=0;i
     
      dist[pos]+map[pos][j])//原始Dijkstra算法的关键判断。			 {   			 	dist[j]=dist[pos]+map[pos][j];//更新最短路径。			 	cost[s][j]=cost[s][pos]+cost[pos][j];//更新费用。			 }			else if(visited[j]==0&&dist[j]==dist[pos]+map[pos][j]&&cost[s][j]>cost[s][pos]+cost[pos][j])//额外条件。			   cost[s][j]=cost[s][pos]+cost[pos][j];//更新费用。		}	}}int main(){   	scanf("%d%d%d%d",&n,&m,&s,&d);	init();		int i,x,y,z,t;	for(i=0;i
     
    
   

相信通过前一阶段每一题都写注释的过程，大家应该已经可以自行领悟代码了，这边我也就不再过多地一一添加注释了。

好了，本次的分享就先到这，大家如果有任何疑问或者建议，欢迎在评论区给我留言。感谢大家捧场！