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

题目链接:   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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#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<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                path[i][j]=j;
                scanf("%d",&dis[i][j]);
                if(dis[i][j]==-1)
                    dis[i][j]=INF;
            }
        }
        for(i=1;i<=n;i++)
            scanf("%d",&V[i]);
        for(k=1;k<=n;k++)
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    t=dis[i][k]+dis[k][j]+V[k];
                    if(t<dis[i][j])
                    {
                        dis[i][j]=t;
                        path[i][j]=path[i][k];     //更新
                    } 
                    else if(t==dis[i][j]&&path[i][k]<path[i][j])  //最小字典序
                        path[i][j]=path[i][k];
                }
            }
        }
        while(scanf("%d%d",&a,&b))
        {
            if(a==-1&&b==-1)
                break;
            printf("From %d to %d :\nPath: %d",a,b,a);
            m=a;
            while(m!=b)
            {
                printf("-->%d",path[m][b]);
                m=path[m][b];
            }
            printf("\nTotal cost : %d\n",dis[a][b]);
            puts("");
        }
    }
    return 0;
}

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

原文：http://blog.csdn.net/qq7366020/article/details/18354979