题意：给你n个城市，一些城市之间会有一些道路，有边权。并且每个城市都会有一些费用。
然后你一些起点和终点，问你从起点到终点最少需要多少路途。 除了起点和终点，最短路的图中的每个城市的费用都要加上。
思路一：因为有多组数据，所以可以采用弗洛伊德算法求多源最短路。 但是，这里要求输出的路径，且按字典序输出。 这里可以用一个数组：pre[i][j]表示i到j的路径上的首个付费城市。这是最关键的地方。
要注意：输出时候,如果起点和终点相同。只输出i，没有箭头。
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int maxn=350; const int INF=0x3f3f3f3f; int n; int citycost[maxn],cost[maxn][maxn]; //citycost[i]表示通过城市i所需要的花费，cost[i][j]表示城市i到j之间的路费 int pre[maxn][maxn]; //pre[i][j]表示i到j的路径中距离i最近的点，也就是i到j的路径中首个交税城市。这是最关键的地方。 //预处理，求出任意两点间的最短路径 void floyd() { int fee; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { pre[i][j]=j; } } for(int k=1; k<=n; k++) { for(int i=1; i<=n; i++) { if(i==k || cost[i][k]==-1) //特判 continue; for(int j=1; j<=n; j++) { if(j==k || cost[j][k]==-1) //特判 continue; fee=cost[i][k]+cost[k][j]+citycost[k]; //当前计算出的花费 if(fee<cost[i][j] || cost[i][j]==-1) { //如果花费比原来的小，或者原来cost[i][j]不直接相连 cost[i][j]=fee; pre[i][j]=pre[i][k]; } else if(fee==cost[i][j] && pre[i][k]<pre[i][j]) { //这里就是为了能够字典序输出 pre[i][j]=pre[i][k]; } } } } } //输出路径 void Path(int i,int j) { if(pre[i][j]==j) { printf("%d-->%d ",i,j); } else { printf("%d-->",i); Path(pre[i][j],j); } } int main() { int r,s,e; while(scanf("%d",&n)!=EOF) { if(n==0) break; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { scanf("%d",&r); cost[i][j]=r; //原本直接存的是上三角矩阵，WA。。。 } } for(int i=1; i<=n; i++) { scanf("%d",&r); citycost[i]=r; } floyd(); while(scanf("%d%d",&s,&e)) { if(s==-1 && e==-1) break; printf("From %d to %d : ",s,e); printf("Path: "); if(s==e) printf("%d ",s); else Path(s,e); //若出发城市非目标城市，依次获取最佳路径上的首个交税城市，并输出 printf("Total cost : %d ",cost[s][e]); } } return 0; }
思路二：使用Bellman-Ford算法计算最小费用路径。
逐边扩展最小费用路径，共迭代n-1次。每次迭代松弛图的所有边。松弛的依据是改变路径的第1个交税城市后，是否会使费用变得更小。若费用相同，则采用交税城市编号较小的方案。
由于题目要求输出路径，因此对每个路径上的节点来说，需要存储下一个交税城市的序号(路径上倒数第二个城市为交税城市，其后继城市是目标城市)
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int maxn=350; const int INF=0x3f3f3f3f; int n; int citycost[maxn],cost[maxn][maxn]; //citycost[i]表示通过城市i所需要的花费，cost[i][j]表示城市i到j之间的路费 struct Route { int nextcity; //该路径的第一个交税城市 int cost; //路径i->j的最小花费 } route[maxn][maxn]; //route[i][j]表示i到j的路径 void init() { int curcost,precost; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i==j) { route[i][j].cost=0; route[i][j].nextcity=j; continue; } if(cost[i][j]>=0) { route[i][j].cost=cost[i][j]; route[i][j].nextcity=j; } else { route[i][j].cost=INF; //如果花费为-1，即两城市不连通，花费设为INF route[i][j].nextcity=-1; } } } /* Bellman-Ford算法，最外层n-1次循环，逐边扩展最短路。 i相当于该算法中的源点s，这里枚举每个节点为源点的情况。 j、k二层循环则相当于BF算法中遍历所有的边 */ for(int t=1; t<n; t++) { for(int i=1; i<=n; i++) { //枚举路径的出发城市i for(int j=1; j<=n; j++) { //枚举该路径的首个交税城市j if(i==j || cost[i][j]<0) continue; for(int k=1; k<=n; k++) { //枚举路径的目标城市 curcost=cost[i][j]+citycost[j]+route[j][k].cost; //当前计算出的i->k的花费 precost=route[i][k].cost; //之前计算的i->k的花费 //若当前花费更小，或虽为同样的花费，但当前花费的交税城市j的序号小，则更新 if(curcost<precost || (curcost==precost && j<route[i][k].nextcity)) { route[i][k].cost=curcost; route[i][k].nextcity=j; } } } } } } int main() { int r,s,e,f,lastf; while(scanf("%d",&n)!=EOF) { if(n==0) break; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++){ scanf("%d",&r); cost[i][j]=r; //原本直接存的是上三角矩阵，WA。。。 } } for(int i=1; i<=n; i++) { scanf("%d",&r); citycost[i]=r; } init(); //s:出发城市 e:目标城市 while(scanf("%d%d",&s,&e)) { if(s==-1 && e==-1) break; printf("From %d to %d : ",s,e); printf("Path: %d",s); //若出发城市非目标城市，依次获取最佳路径上的首个交税城市，并输出 if(s!=e) { for(f=route[s][e].nextcity; f!=e; f=route[f][e].nextcity) { printf("-->%d",f); } printf("-->%d ",f); //最后输出目标城市 } else { printf(" "); //若s==e，直接输出换行 } printf("Total cost : %d ",route[s][e].cost); } } return 0; }