题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1385
题意：给你一张图的邻接矩阵和每个城市的收费，最后给你若干个起点和终点，求最短路径并打印
思路：多源最短路想到的肯定是floyd，用path[i][j]来表示从i到j经过的第一个点是哪个。
代码：
#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using namespace std; typedef long long LL; typedef pair<int, int> P; const int maxn = 1e3 + 5; const int mod = 1e9 + 7; int n; int d[maxn][maxn],tax[maxn],path[maxn][maxn]; void floyd(){ for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ path[i][j]=j; } } for (int k=1;k<=n;k++){ for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ if (d[i][j]>d[i][k]+d[k][j]+tax[k]){ d[i][j]=d[i][k]+d[k][j]+tax[k]; path[i][j]=path[i][k]; } else if (d[i][j]==d[i][k]+d[k][j]+tax[k]){ path[i][j]=min(path[i][j],path[i][k]); } } } } } int main () { while (~scanf ("%d",&n)&&n){ for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ int cost; scanf ("%d",&cost); d[i][j]=cost; if (cost==-1) d[i][j]=INF; } } for (int i=1;i<=n;i++) scanf ("%d",&tax[i]); int s,t; floyd(); while (~scanf ("%d%d",&s,&t)){ if (s==-1&&t==-1) break; printf ("From %d to %d :\nPath: ",s,t); int to=s; while (to!=t){ printf ("%d-->",to); to=path[to][t]; } printf ("%d\n",t); printf ("Total cost : %d\n\n",d[s][t]); } } return 0; }