【floyd记录路径】HDU 1385 Minimum Transport Cost
http://acm.hdu.edu.cn/showproblem.php?pid=1385题意: 找一个路径使得从一个地方坐的士到另一个地方花费最小，其中除了起点和终点，途中经过的站点要收费
Sample Input
5
0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
1 3
3 5
2 4
-1 -1
0
Sample Output
From 1 to 3 :
Path: 1-->5-->4-->3
Total cost : 21
From 3 to 5 :
Path: 3-->4-->5
Total cost : 16
From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17
#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>//#include <map>#include <queue>#include <utility>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;#define inf 999999999 //用0x3fffffff太大溢出，纠结了良久#define M 205int dist, n, b, path;void floyd (){ int i, j, k; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) path = j; //记录路径数组初始化，表示从i到j经过的第一个站 for (k = 1; k <= n; k++) { for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { int tp = dist + dist + b; //溢出之地，因为+了b，其实先判断是否有路会更保险 if (tp < dist) dist = tp, path = path; else if (tp == dist && path < path) path = path; //按字典序记录路径 } } }}int main(){ int i, j, u, v, tp; while (scanf ("%d", &n), n) { for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { scanf ("%d", dist+j); if (dist == -1) dist = inf; } } for (i = 1; i <= n; i++) scanf ("%d", b+i); floyd(); while (scanf ("%d%d", &u, &v), (u != -1 || v != -1)) { printf ("From %d to %d :\n", u, v); printf ("Path: %d", u); tp = u; while (u != v) { printf ("-->%d", path); u = path; } printf ("\nTotal cost : %d\n\n", dist); } } return 0;}
页:
[1]