AcWing 1128. 信使(单源最短路)

2023-12-28 22:21:24

题目链接

活动 - AcWing 本课程系统讲解常用算法与数据结构的应用方式与技巧。icon-default.png?t=N7T8https://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算法提高课

文章来源:https://blog.csdn.net/u012181348/article/details/135277772
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。