hdu1385 Minimum Transport Cost

#include<stdio.h>

const int MAX=105;
int g[MAX][MAX],route[MAX][MAX],tax[MAX];
int n;

void find(int start,int end)
{
    while(route[start][end]!=end)                    
    {                                                
        printf("-->%d",route[start][end]);            
        start=route[start][end];
    }
    printf("-->%d\n",end);
}

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]);
                route[i][j]=j;
            }

        for(int i=1;i<=n;i++)
            scanf("%d",&tax[i]);

        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                if(g[i][k]==-1||i==k) continue;    
                for(int j=1;j<=n;j++)
                {
                    if(g[k][j]==-1||j==k||j==i) continue;
                    if(g[i][j]==-1||g[i][j]>g[i][k]+tax[k]+g[k][j])        //只有在两种情况下才可能更新两点间距

                    {
                        g[i][j]=g[i][k]+tax[k]+g[k][j];
                        route[i][j]=route[i][k];                //route(i,j)记录从i出发到j的路径中紧接着i的点

                    }
                    if(g[i][j]==g[i][k]+tax[k]+g[k][j]&&route[i][j]>route[i][k])
                    {
                        route[i][j]=route[i][k];
                    }
                }
            }
        }

        int start,end;
        while(scanf("%d%d",&start,&end),start!=-1)
        {
            printf("From %d to %d :\n",start,end);
            if(start==end)
                printf("Path: %d\n",start);
            else
            {
                printf("Path: %d",start);
                find(start,end);
            }
            printf("Total cost : %d\n\n",g[start][end]);
        }
    }
    return 0;
}

总结：

原题说起点和终点免税，亦即中间结点收税，恰好对应Floyd算法中通过中间结点来更新两点的间距，在打印路径时可以开辟一个二维数组，其值记录在这两点间的最短路径上的第一个中间结点，之后通过循环依次检索出中间结点。