【题目链接】
ybt 1376：信使(msner)
【题目考点】
1. 图论：最短路径
【解题思路】
每个哨所是一个顶点，哨所与哨所之间的通信线路为边，两哨所间通讯花费的时间为边的权值。
记第一个哨所为顶点s，信息从第一个哨所传递到表示为顶点x的某哨所可能有多条路径，每条传送路径有一个花费的时间，自然要选择花费时间最少的传送方案，也就是图中从顶点s到顶点x的最短路径。
从哨所s到哨所x的送信时间就是顶点s到顶点x的最短路径的长度。
先求出顶点s到图中其他每个顶点的最短路径。
要想完成整个送信过程，就要让所有其他哨所都接收到第一个哨所传出的信，完成整个送信过程的时间就是最晚收到信的哨所的收信时间，也就是顶点s到其它所有顶点的最短路径中路径长度最大值。文章来源：https://www.toymoban.com/news/detail-623272.html
该题n最大为100，可以选择使用Floyd算法，Dijkstra算法，Dijkstra堆优化算法，SPFA算法文章来源地址https://www.toymoban.com/news/detail-623272.html
【题解代码】
解法1：Floyd算法
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 105
int n, m, edge[N][N], dis[N][N];//dis[i][j]:i到j的最短路径长度
void floyd()
{
memset(dis, 0x3f, sizeof(dis));
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
{
if(i == j)
dis[i][j] = 0;
else if(edge[i][j])
dis[i][j] = edge[i][j];
}
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(dis[i][j] > dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
int main()
{
int f, t, w, mxDis = 0;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> f >> t >> w;
edge[f][t] = edge[t][f] = w;
}
floyd();
for(int i = 1; i <= n; ++i)
{
if(dis[1][i] == INF)//从顶点1到顶点i没有路径
{
cout << -1;
return 0;
}
if(mxDis < dis[1][i])//mxDis:从1出发的最短路径中的最大值
mxDis = dis[1][i];
}
cout << mxDis;
return 0;
}
解法2：Dijkstra算法
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
struct Edge//边结点
{
int v, w;
Edge(){}
Edge(int a, int b):v(a),w(b){}
};
vector<Edge> edge[N];//邻接表
int n, m;//n:顶点数 m:边数
int dis[N];//dis[i]:源点到顶点i的最短路径
bool vis[N];//vis[i]:源点到顶点i的最短路径是否已经确定
void dijkstra(int sv)//sv：起始点
{
memset(dis, 0x3f, sizeof(dis));
dis[sv] = 0;
for(int k = 1; k <= n; ++k)
{
int u = 0;
for(int i = 1; i <= n; ++i)
if(vis[i] == false && (u == 0 || dis[i] < dis[u]))
u = i;
vis[u] = true;
for(Edge e : edge[u])
{
int v = e.v, w = e.w;
if(vis[v] == false && dis[v] > dis[u]+w)
dis[v] = dis[u]+w;
}
}
}
int main()
{
int f, t, w, mxDis = 0;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> f >> t >> w;
edge[f].push_back(Edge(t, w));
edge[t].push_back(Edge(f, w));
}
dijkstra(1);
for(int i = 1; i <= n; ++i)
{
if(dis[i] == INF)//从顶点1到顶点i没有路径
{
cout << -1;
return 0;
}
mxDis = max(mxDis, dis[i]);//mxDis:从1出发的最短路径中的最大值
}
cout << mxDis;
return 0;
}
解法3：Dijkstra算法堆优化
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
struct Pair
{
int u, d;//u:顶点 d:距离
Pair(){}
Pair(int a, int b):u(a),d(b){}
bool operator < (const Pair &b) const//优先队列中 d更小的更优先
{
return b.d < d;
}
};
struct Edge
{
int v, w;
Edge(){}
Edge(int a, int b):v(a),w(b){}
};
vector<Edge> edge[N];
bool vis[N];//vis[i]表示从v0到i点的最短路径是否已经确定
int n, m, dis[N];//v0:源点 dis[i]：当前情况下v0到i的最短路径距离
void dijkstra(int sv)//sv起始点
{
priority_queue<Pair> pq;//优先队列中 d更小的更优先
memset(dis, 0x3f, sizeof(dis));//dis初始值为INF
dis[sv] = 0;
pq.push(Pair(sv, 0));
while(pq.empty() == false)
{
int u = pq.top().u;
pq.pop();
if(vis[u])//如果顶点u已经访问过，则跳过
continue;
vis[u] = true;
for(Edge e : edge[u])
{
int v = e.v, w = e.w;
if(vis[v] == false && dis[v] > dis[u]+w)
{
dis[v] = dis[u]+e.w;
pq.push(Pair(v, dis[v]));
}
}
}
}
int main()
{
int f, t, w, mxDis = 0;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> f >> t >> w;
edge[f].push_back(Edge(t, w));
edge[t].push_back(Edge(f, w));
}
dijkstra(1);
for(int i = 1; i <= n; ++i)
{
if(dis[i] == INF)//从顶点1到顶点i没有路径
{
cout << -1;
return 0;
}
mxDis = max(mxDis, dis[i]);//mxDis:从1出发的最短路径中的最大值
}
cout << mxDis;
return 0;
}
解法4：SPFA算法
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
struct Edge
{
int v, w;
Edge(){}
Edge(int a, int b):v(a),w(b){}
};
vector<Edge> edge[N];
bool vis[N];//vis[i]：顶点i是否在队列中
int n, m, dis[N];//dis[i]：当前情况下v0到i的最短路径距离
void spfa(int sv)//sv起始点
{
memset(dis, 0x3f, sizeof(dis));//dis初始值为INF
queue<int> que;
dis[sv] = 0;
vis[sv] = true;
que.push(sv);
while(que.empty() == false)
{
int u = que.front();
que.pop();
vis[u] = false;
for(Edge e : edge[u])
{
int v = e.v, w = e.w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if(vis[v] == false)
{
vis[v] = true;
que.push(v);
}
}
}
}
}
int main()
{
int f, t, w, mxDis = 0;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> f >> t >> w;
edge[f].push_back(Edge(t, w));
edge[t].push_back(Edge(f, w));
}
spfa(1);
for(int i = 1; i <= n; ++i)
{
if(dis[i] == INF)//从顶点1到顶点i没有路径
{
cout << -1;
return 0;
}
mxDis = max(mxDis, dis[i]);//mxDis:从1出发的最短路径中的最大值
}
cout << mxDis;
return 0;
}
到了这里，关于信息学奥赛一本通 1376：信使(msner)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
