本题就是使用Floyd算法求所有路径的最短路径，并且需要保存路径，而且更进一步需要按照字典顺序输出结果。

还是有一定难度的。

Floyd有一种很巧妙的记录数据的方法，大多都是使用这个方法记录数据的。

不过其实本题数据不是很大，一般太大的数据也无法使用Floyd，因为效率是O(N^3)。

所以其实也可以使用一般的Floyd算法，然后增加个三维数组记录数据。下面就是这种做法，0ms过了.

#include 
  
   
#include 
   
     using std::vector; vector
    
      checkDictOrder(vector
     
       a, vector
      
        b) { for (int i = 0; i < (int)a.size() && i < (int)b.size(); i++) { if (a[i] < b[i]) return a; else if (a[i] > b[i]) return b; } return a.size() < b.size() ? a : b; } void FloydWarshall(vector
       
         > &gra, vector
        
          &tax, vector
         
           > > &paths) { int N = (int)gra.size(); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (-1 != gra[i][j]) { paths[i][j].push_back(i); paths[i][j].push_back(j); } } } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if ( -1 != gra[i][k] && -1 != gra[k][j] && (-1 == gra[i][j] || gra[i][k] + gra[k][j] + tax[k] <= gra[i][j])) { vector
          
            t = paths[i][k]; t.pop_back();//pop k out t.insert(t.end(), paths[k][j].begin(), paths[k][j].end()); if (gra[i][k]+gra[k][j]+tax[k]==gra[i][j]) paths[i][j] = checkDictOrder(t, paths[i][j]); else paths[i][j] = t; gra[i][j] = gra[i][k] + gra[k][j] + tax[k]; } } } } } int main() { int N, g, h; while (scanf("%d", &N) && N) { vector
           
             > gra(N, vector
            
             (N)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%d", &gra[i][j]); } } vector
             
               tax(N); for (int i = 0; i < N; i++) { scanf("%d", &tax[i]); } vector
              
                > > paths(N, vector
               
                 >(N)); FloydWarshall(gra, tax, paths); while (scanf("%d %d", &g, &h) && g != -1 && h != -1) { printf("From %d to %d :\nPath: ", g, h); g--, h--; if(g != h) { for (int u = 0; u+1 < (int)paths[g][h].size(); u++) { printf("%d-->", paths[g][h][u]+1); } } printf("%d\nTotal cost : %d\n\n", h+1, gra[g][h]); } } return 0; }