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

輸入格式:
輸入說明：輸入數(shù)據(jù)的第1行給出4個正整數(shù)N、M、S、D，其中N（2≤N≤500）是城市的個數(shù)，順便假設(shè)城市的編號為0~(N?1)；M是高速公路的條數(shù)；S是出發(fā)地的城市編號；D是目的地的城市編號。隨后的M行中，每行給出一條高速公路的信息，分別是：城市1、城市2、高速公路長度、收費額，中間用空格分開，數(shù)字均為整數(shù)且不超過500。輸入保證解的存在。

輸出格式:
在一行里輸出路徑的長度和收費總額，數(shù)字間以空格分隔，輸出結(jié)尾不能有多余空格。

輸入樣例:
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

這篇沒有注釋，看不懂代碼的移步我的甲級專欄里的1003 Emergency (25 分)，那個有詳細的注釋。

//迪杰斯特拉算法求7-3 旅游規(guī)劃 (25 分) #include <stdio.h> #include <string.h> #include<stdbool.h> #define maxn 0x3f3f3f3f int n; int L[1001][1001]; //城市之間的距離 int W[1001][1001]; //城市之間的收費 int LL[1001]; //到起點的最近距離 int WW[1001]; //到起點的最近距離的收費 int flag[1001]; //是否走過 void Dijkstra(int x) {memset(flag, false, sizeof(flag));memset(LL,maxn,sizeof(LL));LL[x] = 0;for (int j = 0; j < n; j++){int u = -1, min = maxn;for (int i = 0; i < n; i++){if (flag[i] == false && LL[i] < min){u = i;min = LL[i];}}if (u == -1)return;flag[u] = true;for (int i = 0; i < n; i++){if (L[u][i] != 0 && flag[i] == false){if (L[u][i] + LL[u] < LL[i]){LL[i] = L[i][u] + LL[u];WW[i] = W[i][u] + WW[u];}else if (L[u][i] + LL[u] == LL[i]){if (WW[u] + W[u][i] < WW[i]){WW[i] = W[u][i] + WW[u];}}}}} } int main() {int m, s, d;scanf("%d %d %d %d", &n, &m, &s, &d);memset(L, maxn, sizeof(L));while (m--){int a, b, l, w;scanf("%d %d %d %d", &a, &b, &l, &w);L[a][b] = l, L[b][a] = l;W[a][b] = w, W[b][a] = w;}Dijkstra(s);printf("%d %d", LL[d], WW[d]); }

總結(jié)

以上是生活随笔為你收集整理的7-3 旅游规划 (25 分)（C语言实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。