hdu 1385 Minimum Transport Cost (最小字典序最短路径)

Tags: c++

题目链接: hdu 1385

题目大意: 给出N个点的邻接矩阵,求任意两点的最短路径

若有多条路径,输出字典序最小的路径

解题思路: 边为-1的时候,换成INF,用Floyd求出最短路径,path[ i ][ j ]表示路径i到j经过的点

dis[ i ][ j ]=Min( dis[ i ][ j ],dis[ i ][ k ] + dis[ k ][ j ] ),更新了dis[ i ][ j ]之后,记录path[ i ][ j ]=path[ i ][ k ]

代码:

#include 
#include 
#include 
#define MAX 205
#define INF 0x3f3f3f3f
int dis[MAX][MAX],path[MAX][MAX];
int main()
{
    int i,j,n,m,k,t,V[MAX],a,b;
    while(scanf("%d",&n)!=EOF&&n)
    {
        for(i=1;i%d",path[m][b]);
                m=path[m][b];
            }
            printf("\nTotal cost : %d\n",dis[a][b]);
            puts("");
        }
    }
    return 0;
}


本文链接:http://www.4byte.cn/learning/58672.html