有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。
输入格式:
输入说明:输入数据的第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
|
输出样例:
思路:
直接套用Dijkstra就好
代码:
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
| #include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; const int N = 505; int n,m,S,D,dis[N],pay[N]; int mar[N][N],price[N][N]; bool visited[N]; void Dijkstra(){ for(int i = 0 ; i < n ; ++i){ dis[i] = mar[S][i]; pay[i] = price[S][i]; } memset(visited,false,sizeof(visited)); visited[S] = 1; for(int i = 0 ; i < n - 1; ++i){ int pos = -1,cnt = INF; for(int j = 0 ; j < n ; ++j){ if(!visited[j] && dis[j] < cnt){ pos = j; cnt = dis[j]; } } if(pos == -1) break; visited[pos] = true; for(int j = 0; j < n; ++j){ if(!visited[j]){ if(dis[j] > dis[pos] + mar[pos][j]){ dis[j] = dis[pos] + mar[pos][j]; pay[j] = pay[pos] + price[pos][j]; }else if(dis[j] == dis[pos] + mar[pos][j] && pay[j] > pay[pos] + price[pos][j]) pay[j] = pay[pos] + price[pos][j]; } } } cout << dis[D] << " " << pay[D] << endl; } int main(){ cin >> n >> m >> S >> D; memset(mar,0x3f,sizeof(mar)); for(int i = 0 ; i < m ; ++i){ int a,b,c,d; cin >> a >> b >> c >> d; mar[a][b] = mar[b][a] = c; price[a][b] = price[b][a] = d; } Dijkstra(); return 0; }
|