HDU 1385 Minimum Transport Cost(Floyd+打印字典序最小路径)

HDU 1385 Minimum Transport Cost(Floyd+打印字典序最小路径)

http://acm.hdu.edu.cn/showproblem.php?pid=1385

题意:给你一个无向图,现在要你输出特定起点到终点的最短距离以及字典序最小的路径.不过本题的两路径之间的距离计算方式与常规不同.

分析:

直接用Floyd算法计算最短路径,且保存字典序最小的path路径即可.代码需要熟练掌握.

AC代码:

#include<cstdio>
#include<cstring>
#define INF 1e9
using namespace std;
const int maxn = 100+20;
int n;
int cost[maxn];
int dist[maxn][maxn];//最短距离
int path[maxn][maxn];//path[i][j]保存了从i到j路径的第一个点(除i以外)
void floyd()
{
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        path[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(dist[i][k]<INF && dist[k][j]<INF)
    {
        if(dist[i][j] > dist[i][k]+dist[k][j]+cost[k])
        {
            dist[i][j] = dist[i][k]+dist[k][j]+cost[k];
            path[i][j] = path[i][k];
        }
        else if(dist[i][j] == dist[i][k]+dist[k][j]+cost[k] && path[i][j]>path[i][k])
        {
            path[i][j]=path[i][k];
        }
    }

}
int main()
{
    while(scanf("%d",&n)==1&&n)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&dist[i][j]);
                if(dist[i][j]==-1) dist[i][j]=INF;
            }
        for(int i=1;i<=n;i++)
            scanf("%d",&cost[i]);

        floyd();

        while(true)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            if(u==-1&&v==-1) break;

            printf("From %d to %d :\n",u,v);
            if(u!=v)
            {
                printf("Path: %d",u);
                int beg = path[u][v];
                while(true)
                {
                    printf("-->%d",beg);
                    if(beg==v) { printf("\n"); break; }
                    beg = path[beg][v];
                }
            }
            else    //注意U==V的特殊情况
            {
                printf("Path: %d\n",u);
            }
            printf("Total cost : %d\n\n",dist[u][v]);
        }

    }
    return 0;
}