貨物運(yùn)輸

時(shí)間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：4 描述

S國(guó)有n個(gè)城市，從a城到b城運(yùn)貨的花費(fèi)有兩部分組成：

（1）a城到b城的運(yùn)輸費(fèi)

（2）途徑城市的稅收

例如：a?運(yùn)貨到?b，走路線a?—>?i?—>?j?—>?b?,總花費(fèi)為a?到?i?，i?到?j，j?到?b?的運(yùn)輸費(fèi)、i，j?城市的稅收之和。

已知任意兩個(gè)城市的運(yùn)輸費(fèi)用，每個(gè)城市的稅收，計(jì)算出，城市a到b的最小運(yùn)輸費(fèi)。

輸入

多組數(shù)據(jù)。
第一行輸入整數(shù)n(n不大于200，城市從1開(kāi)始編號(hào))
接下來(lái)輸入n行n列的矩陣M，Mij 表示 i 城市到 j 城市的運(yùn)輸費(fèi)，-1表示這兩個(gè)城市不能直接到達(dá)。
第n+2 行 輸入n個(gè)整數(shù)，第i個(gè)整數(shù)代表第i個(gè)城市的稅收。
第n+3 行 輸入整數(shù)m，表示有m次詢問(wèn)（m不大于200）。
接下來(lái)m行，每行輸入兩個(gè)整數(shù)u， v。

輸出

對(duì)于每次詢問(wèn)
輸出如下：
From u to v :
Path: u-->c1-->......-->ck-->v
Total cost :?

............

From e to f :
Path: e-->e1-->..........-->ek-->f
Total cost : ......


Note: 如果有多種路徑方案，輸出字典序最小的，每次詢問(wèn)后加一個(gè)換行。a城市到a城市的運(yùn)費(fèi)不一定為0

樣例輸入

4 0 5 15 -1 5 0 5 8 15 10 2 5 -1 -1 8 0 5 3 7 1 3 1 3 2 4 3 1

樣例輸出

From 1 to 3 : Path: 1-->2-->3 Total cost : 13From 2 to 4 : Path: 2-->4 Total cost : 8From 3 to 1 : Path: 3-->1 Total cost : 15

解題思路：Floyd+路徑輸出

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 200; const int inf = 0x3f3f3f3f; int n,m,dis[maxn][maxn],tax[maxn]; int path[maxn][maxn]; // 用path[i][j] 記錄路徑i-->j的i的下一個(gè)經(jīng)過(guò)的節(jié)點(diǎn)。 // 這樣的話，如果說(shuō)一條路徑是這樣的： i->a->b->j // 那path的值就是: path[i][j] = a , path[a][j] = b , path[b][j] = j; void floyd() {for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){if(dis[i][j] > dis[i][k] + dis[k][j] + tax[k]){path[i][j] = path[i][k];dis[i][j] = dis[i][k] + dis[k][j] + tax[k];}else if(dis[i][j] == dis[i][k] + dis[k][j] + tax[k]){if(path[i][j] > path[i][k])path[i][j] = path[i][k];}} }int main() {int a,b;while(scanf("%d",&n)!=EOF){for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){scanf("%d",&dis[i][j]);if(dis[i][j] != -1)path[i][j] = j;else dis[i][j] = inf;}for(int i = 1; i <= n; i++)scanf("%d",&tax[i]);floyd();scanf("%d",&m);while(m--){scanf("%d %d",&a,&b);printf("From %d to %d :\n", a, b); if(a == b) printf("Path: %d\n", a);else{printf("Path: %d-->", a); int next = path[a][b];while(next != b){printf("%d-->", next); next = path[next][b]; }printf("%d\n",b);}printf("Total cost : %d\n", dis[a][b]); printf("\n"); }}return 0; }

與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的nyoj 931 货物运输(Floyd输出路径)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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