hdu Minimum Transport Cost(按字典序输出路径) - c++编程基础

求最短路，要求输出字典序最小的路径。

spfa：拿一个pre[]记录前驱，不同的是在松弛的时候，要考虑和当前点的dis值相等的情况，解决的办法是dfs找出两条路径中字典序较小的，pre[]去更新。把路径当做字符串处理。

我只用之前的pre去更新当前点，并没考虑到起点到当前点的整个路径，其实这样并不能保证是字典序最小。wa了N次，于是乎搜了下题解，发现用spfa解的很少，看到了某大牛的解法如上，感觉很赞的想法。

#include 
  
   
#include 
   
     #include 
    
      #include
      #include 
      
        #include 
       
         #include 
        
          #include 
         
           #define LL long long #define _LL __int64 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 110; int n; int tax[maxn]; int Map[maxn][maxn]; int dis[maxn],inque[maxn]; int pre[maxn]; int pos = 0; void dfs(int u, char *s) { if(u == -1) return; dfs(pre[u],s); s[pos++] = u+'0'; } bool solve(int v, int u) { char s1[maxn],s2[maxn]; //寻找先前的路径 pos = 0; dfs(v,s1); s1[pos] = ''; //寻找由u更新的路径 pos = 0; dfs(u,s2); s2[pos++] = v+'0'; s2[pos] = ''; if(strcmp(s1,s2) > 0) return true; return false; } int spfa(int s, int t) { queue 
          
            que; memset(dis,INF,sizeof(dis)); memset(inque,0,sizeof(inque)); memset(pre,-1,sizeof(pre)); dis[s] = 0; inque[s] = 1; que.push(s); while(!que.empty()) { int u = que.front(); que.pop(); inque[u] = 0; for(int v = 1; v <= n; v++) { if(Map[u][v] > 0) { int tmp = dis[u] + Map[u][v] + tax[v]; if(tmp < dis[v])//直接更新 { dis[v] = tmp; pre[v] = u; if(!inque[v]) { inque[v] = 1; que.push(v); } } else if(tmp == dis[v] && solve(v,u)) { pre[v] = u; } } } } return dis[t]; } void output(int s, int t) { int res[maxn]; int cnt = 0; int tmp = t; while(pre[tmp] != -1) { res[cnt++] = tmp; tmp = pre[tmp]; } res[cnt] = s; printf(Path: ); for(int i = cnt; i >= 1; i--) printf(%d-->,res[i]); printf(%d ,res[0]); } int main() { while(~scanf(%d,&n) && n) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) scanf(%d,&Map[i][j]); } for(int i = 1; i <= n; i++) scanf(%d,&tax[i]); int u,v; while(~scanf(%d %d,&u,&v)) { if(u == -1 && v == -1) break; int tmp1 = tax[u];//备份 int tmp2 = tax[v]; tax[u] = 0; tax[v] = 0; printf(From %d to %d : ,u,v); int ans = spfa(u,v); output(u,v); printf(Total cost : %d ,ans); //恢复备份 tax[u] = tmp1; tax[v] = tmp2; } } return 0; }

floyd:pre[i][j]记录i到j路径上距离i最近的点，输出路径时按pre正向输出。感觉floyd很强大啊，还可以这样记录路径。

#include 
  
   
#include 
   
     #include 
    
      #include
      #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #define LL long long #define _LL __int64 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 110; int Map[maxn][maxn]; int tax[maxn]; int pre[maxn][maxn]; int n; void floyd() { //初始化 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++) { for(int j = 1; j <= n; j++) { if(Map[i][k] > 0 && Map[k][j] > 0) { int tmp = Map[i][k] + Map[k][j] + tax[k]; if(tmp < Map[i][j]) //小于直接更新 { Map[i][j] = tmp; pre[i][j] = pre[i][k]; } else if(tmp == Map[i][j]) { pre[i][j] = min(pre[i][k],pre[i][j]); } } } } } } void output(int s, int t) { printf(Path: ); int tmp = s; while(tmp != t) { printf(%d-->,tmp); tmp = pre[tmp][t]; } printf(%d ,t); } int main() { while(~scanf(%d,&n) && n) { for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { scanf(%d,&Map[i][j]); if(Map[i][j] == -1) Map[i][j] = INF; } for(int i = 1; i <= n; i++) scanf(%d,&tax[i]); int u,v; floyd(); while(~scanf(%d %d,&u,&v)) { if(u == -1 && v == -1) break; printf(From %d to %d : ,u,v); output(u,v); printf(Total cost : %d ,Map[u][v]); } } return 0; }