07-圖6 旅游規劃 (25 分)

有了一張自駕旅游路線圖，你會知道城市間的高速公路長度、以及該公路要收取的過路費。現在需要你寫一個程序，幫助前來咨詢的游客找一條出發地和目的地之間的最短路徑。如果有若干條路徑都是最短的，那么需要輸出最便宜的一條路徑。

輸入格式:

輸入說明：輸入數據的第1行給出4個正整數N、M、S、D，其中N（2）是城市的個數，順便假設城市的編號為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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 550;
const int INF = 1000000000;int G[maxn][maxn],cost[maxn][maxn];
int d[maxn],c[maxn];
bool vis[maxn] = {0};
int n,m,st,ed;void Dijkstra( int st);int main(){scanf("%d%d%d%d",&n,&m,&st,&ed);fill(G[0],G[0]+maxn*maxn,INF);int u,v;for(int i = 0; i < m; i++){scanf("%d%d%",&u,&v);scanf("%d%d",&G[v][u],&cost[v][u]);G[u][v] = G[v][u];cost[u][v] = cost[v][u];}Dijkstra(st);printf("%d %d",d[ed],c[ed]);return 0;
}void Dijkstra(int st){fill(d,d+maxn,INF);fill(c,c+maxn,INF);d[st] = 0;c[st] = 0;for(int i = 0; i < n; i++){int u = -1, min = INF;for(int j = 0; j < n; j++){if(!vis[j] && d[j] < min){u = j;min = d[j];}}if(u == -1) return;vis[u] = true;for(int v = 0; v < n; v++){if(!vis[v] && G[u][v] != INF){if(d[v] > d[u] + G[u][v]){d[v] = d[u] + G[u][v];c[v] = c[u] + cost[u][v];}else if(d[v] == d[u] + G[u][v]){if(c[v] > c[u] + cost[u][v]){c[v] = c[u] + cost[u][v];}}}}}
}

?