HDU 1385 Minimum Transport Cost（Floyd 最短路 打印路径）

HDU 1385

 

大意：

有N个城市，然后直接给出这些城市之间的邻接矩阵，矩阵中-1代表那两个城市无道路相连，其他值代表路径长度。

如果一辆汽车经过某个城市，必须要交一定的钱(可能是过路费)。

现在要从a城到b城，花费为路径长度之和，再加上除起点与终点外所有城市的过路费之和。

求最小花费，如果有多条路经符合，则输出字典序最小的路径。

 

思路：

Floyd求最短路，打印路径即可。

 

/*------------------------------------------------------------------*/

const int maxn = 1000;
int n, s, e;
int path[maxn][maxn];
int b[maxn];
int rode[maxn][maxn];

void Solve()
{
    while(~scanf("%d", &n) && n)
    {
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                scanf("%d", &path[i][j]);
                if(path[i][j] == -1)
                {
                    path[i][j] = INF;
                }
                rode[i][j] = j;
            }
        }
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &b[i]);
        }
        for(int k = 1; k <= n; ++k)
        {
            for(int i = 1; i <= n; ++i)
            {
                for(int j = 1; j <= n; ++j)
                {
                    if(path[i][k]+path[k][j]+b[k] < path[i][j])
                    {
                        path[i][j] = path[i][k]+path[k][j]+b[k];
                        rode[i][j] = rode[i][k];
                    }
                    else if(path[i][j] == path[i][k]+path[k][j]+b[k] && rode[i][j] > rode[i][k])
                    {
                        rode[i][j] = rode[i][k];
                    }
                }
            }
        }
        while(~scanf("%d%d", &s, &e))
        {
            if(s == -1 && e == -1)
                break;
            printf("From %d to %d :\nPath: %d", s, e, s);
            int u = s, v = e;
            while(s != e)
            {
                printf("-->%d", rode[s][e]);
                s = rode[s][e];
            }
            printf("\n");
            printf("Total cost : %d\n\n", path[u][v]);
        }
    }
}

/*------------------------------------------------------------------*/