题意：已知一邻接矩阵，g[i][j]表示从 i 城道 j 城所需要的花费，b[ i ] 是从 i 城市路过（不是起始城市，也不是终点城市）要交的税。接着有若干询问，给出起点城市和终点城市，问最少花费，并输出该路径，如果有多条最短路径，输出字典序最小的。最后输出最小花费。
思路：Floyd求a->b最短路，长度相等时比较字典序，re[i][j] = k 表示从 i 到 j 是 i 先到 k 再到 j 的。
#include<bits/stdc++.h> using namespace std; const int N=1005,INF=0X3f3f3f3f; int g[N][N],b[N],re[N][N];re[i][j]=k表示从i到j是i先到k再到j的 int n; void floyd(){ for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(g[i][k]+g[k][j]+b[k]<g[i][j]){ g[i][j]=g[i][k]+g[k][j]+b[k]; re[i][j]=re[i][k]; }else{ if(g[i][j]==g[i][k]+g[k][j]+b[k]&&re[i][j]>re[i][k]) re[i][j]=re[i][k]; } } } } } int main(){ while(scanf("%d",&n),n){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ scanf("%d",&g[i][j]); if(g[i][j]==-1) g[i][j]=INF; re[i][j]=j;// } } for(int i=1;i<=n;++i) scanf("%d",&b[i]); floyd(); int s,t; while(scanf("%d%d",&s,&t),s!=-1){// printf("From %d to %d :\nPath: %d",s,t,s); int u=s,v=t; while(u!=v){ printf("-->%d",re[u][v]); u=re[u][v]; } printf("\nTotal cost : %d\n\n",g[s][t]); } } return 0; }看到网上有人给re[][]写了个递归打印函数如下
void print_path(int u , int v){ //u是起点v是终点 int k; if(u==v){ printf("%d",v); return ; } k=path[u][v]; printf("%d-->",u); print_path(k,v); }想到老师说的“尾递归可以改写成递推” 2333
