「最短路」农场派对

本题为1月4日22寒假集训每日一题题解

题目来源:(未知)

题面

题目描述

N(1<=N<=1000)头牛要去参加一场在编号为x(1<=x<=N)的牛的农场举行的派对。有M(1<=M<=100000)条有向道路，每条路长 Ti(1<=Ti<=100)；每头牛都必须参加完派对后回到家，每头牛都会选择最短路径。求这N头牛的最短路径（一个来回）中最长的一条的长度。

特别提醒：可能有权值不同的重边。

输入

第1行：

3个空格分开的整数N,M,X；

第2…M+1 行：
33 个空格分开的整数Ai,Bi,Ti，表示有一条从Ai到Bi的路，长度为Ti。

输出

一行一个数，表示最长最短路的长度。

样例输入

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

样例输出

10

思路分析

显然这是多源最短路问题,可以通过多次使用dijkstra算法解决.

不过此题的数据量是一个稠密图,我个人估了一下,虽然有点悬,但是或许可以使用写起来相对简单的Floyd算法,且Floyd算法本身就是用来解决多源最短路问题的.尝试了一下后发现,可以正好卡着时间界过去,所以就没有写dijkstra算法了.

参考代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int g[1010][1010]; // 邻接矩阵,用vector会TLE

int main()
{
    ios::sync_with_stdio(false);

    int n, m, x;
    cin >> n >> m >> x;

    memset(g, 0x3f, sizeof(g)); // 默认值设置为无穷大

    while (m--)
    {
        int a, b, t;
        cin >> a >> b >> t;
        g[a][b] = min(g[a][b], t);
    }

    for (int i = 1; i <= n; i++)
    {
        g[i][i] = 0; // 自己到自己的距离为0
    }

    // floyd算法
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }

    // 遍历每一个点,找最长的最短路
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        res = max(res, g[i][x] + g[x][i]);
    }

    cout << res << "\n";

    return 0;
}

"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德