有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。
输入格式: 输入说明:输入数据的第1行给出4个正整数N 、M 、S 、D ,其中N (2≤N ≤500)是城市的个数,顺便假设城市的编号为0~(N −1);M 是高速公路的条数;S 是出发地的城市编号;D 是目的地的城市编号。随后的M 行中,每行给出一条高速公路的信息,分别是:城市1、城市2、高速公路长度、收费额,中间用空格分开,数字均为整数且不超过500。输入保证解的存在。
输出格式: 在一行里输出路径的长度和收费总额,数字间以空格分隔,输出结尾不能有多余空格。
输入样例: 1 2 3 4 5 6 4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20结尾无空行
输出样例:
思路 两个权值的最短路径问题。当路径长度不相同时,我们要最短的;当路径长度相同时,我们要花费最少的。
G存储距离,cost存储花费。lowcost[ idx ] [0]存储路径长度,lowcost[idx] [1]存储收费总额。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 #include <iostream> #include <cstring> using namespace std ;const int maxn = 500 +5 ;const int inf=0x3f3f3f3f ;int G[maxn][maxn],cost[maxn][maxn];int vis[maxn];int lowcost[maxn][2 ];int n;void dijkstra (int s,int d) { vis[s]=1 ; for (int i=0 ;i<n;++i) { if (G[s][i]!=inf) { lowcost[i][0 ]=G[s][i],lowcost[i][1 ]=cost[s][i]; } else lowcost[i][0 ]=inf; } for (int cnt=0 ;cnt<n-1 ;++cnt) { int mini=inf,idx=-1 ; for (int i=0 ;i<n;++i) { if (!vis[i]&&lowcost[i][0 ]<mini) { mini=lowcost[i][0 ]; idx=i; } } if (idx==-1 ) return ; vis[idx]=1 ; for (int i=0 ;i<n;++i) { if (!vis[i]&&lowcost[idx][0 ]+G[idx][i]<=lowcost[i][0 ]) { if (lowcost[idx][0 ]+G[idx][i]<lowcost[i][0 ]) lowcost[i][0 ]=lowcost[idx][0 ]+G[idx][i],lowcost[i][1 ]=lowcost[idx][1 ]+cost[idx][i]; else { if (lowcost[idx][1 ]+cost[idx][i]<lowcost[i][1 ]) lowcost[i][0 ]=lowcost[idx][0 ]+G[idx][i],lowcost[i][1 ]=lowcost[idx][1 ]+cost[idx][i]; } } } } printf ("%d %d" ,lowcost[d][0 ],lowcost[d][1 ]); } int main () { for (int i=0 ;i<maxn;++i) memset (G,0x3f ,sizeof (G)); int e,s,d; cin >>n>>e>>s>>d; while (e--) { int a,b,l,w; cin >>a>>b>>l>>w; G[a][b]=G[b][a]=l,cost[a][b]=cost[b][a]=w; } dijkstra(s,d); }