AcWing 1128. 信使（单源最短路）

题目链接

活动 - AcWing 本课程系统讲解常用算法与数据结构的应用方式与技巧。https://www.acwing.com/problem/content/1130/

题解

本质上是一个广播模型。对于每个点来说，它接收到信的时间，等于它到指挥部的最短距离。所有这些点的最短距离取一个最大值，就可以得到最晚接收到信息的时间。本题是单源最短路问题，根据数据范围，本题可以用Dijkstra算法、SPFA算法，也可以用代码简单的Floyd算法来解决。

代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int d[N][N];

int main()
{
    cin >> n >> m;
    
    memset(d, 0x3f, sizeof d);
    for (int i = 1; i <= n; i++) d[i][i] = 0;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = d[b][a] = min(d[a][b], c);
    }
    
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    
    int res = 0;
    for (int i = 1; i <= n; i++)
        if (d[1][i] == INF)
        {
            res = -1;
            break;
        }
        else res = max(res, d[1][i]);
    
    cout << res << endl;
    
    return 0;
}

参考资料

1. AcWing算法提高课