題目分析

來源：acwing

分析：廣播模型，求整個網(wǎng)絡(luò)所有點都被廣播到，需要多少時間。

本題核心：對于每個點來說，它接收到信的時間，是等于它到指揮部的最短距離。

所以，所有點被廣播到，就是求指揮部到所有點的最短路，然后求其最大值。

ac代碼

#include<bits/stdc++.h> using namespace std; const int N = 110; bool st[N]; int res = -1; int dist[N]; int g[N][N]; int n, m;void dijkstra(){memset(dist, 0x3f, sizeof dist);dist[1] = 0;for(int i = 0; i< n; i ++){int t = -1;for(int j = 1; j <= n; j ++)if(!st[j] && (t ==-1 || dist[t] > dist[j]))t = j;st[t] = true;for(int j = 1; j <= n; j ++)dist[j] = min(dist[j], dist[t] + g[t][j]);} }int main(){cin >> n >> m;memset(g, 0x3f, sizeof g);while(m --){int a, b, c;cin >> a >> b >> c;g[a][b] = g[b][a] = min(g[a][b], c);}dijkstra();for(int i = 1; i <= n; i++) res = max(res ,dist[i]);if( res == 0x3f3f3f3f) res = -1;cout << res << endl; }

題目來源

https://www.acwing.com/problem/content/1130/

總結(jié)

以上是生活随笔為你收集整理的算法提高课-图论-单源最短路的建图方式-AcWing 1128. 信使：dijkstra、 最短路取最大值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。