题目描述
N 头牛要去参加在某农场举行的一场编号为 X 的牛的派对。
有 M 条有向道路,每条路长 Ti;每头牛参加完派对后都必须回到家,每头牛都会选择最短路径。
求这 N 头牛的最短路径(一个来回)中最长的一条的长度。
特别提醒:可能有权值不同的重边。
输入格式
第一行包含三个整数 N,M,X。
接下来 M 行,每行包含三个整数 Ai,Bi,Ti,表示有一条从 Ai 到 Bi 的路,长度为 Ti。
输出格式
共一行,一个数,表示最短路中最长的一条的长度。
数据范围
1≤N≤1000,
1≤X≤N,
1≤M≤105,
1≤Ti≤100
样例
输入样例:
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
spfa 求多源最短路径
全部枚举每只牛到农场的距离求max即可
注意:是有向图
距离应该是 dis(起点->终点)+dis(终点->起点)
C++ 代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 101000;
int e[N], ne[N], h[N], w[N], dist[N], idx;
bool st[N];
int n, m, x;
void add(int a, int b, int c)
{
e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}
int spfa(int x, int y)
{
queue<int> q;
memset(dist, 0x3f, sizeof(dist));
dist[x] = 0;
q.push(x);
st[x] = true;
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return dist[y];
}
int main()
{
int maxn = -1;
cin >> n >> m >> x;
memset(h, -1, sizeof(h));
for (int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
for (int i = 1; i <= n; i++)
{
memset(st, 0, sizeof(st));
if (i == x)
continue;
int t = spfa(i, x) + spfa(x, i);
if (t > maxn)
maxn = t;
}
cout << maxn;
return 0;
}
为什么 堆优化版Dijkstra 这么写 会 T 呢?