算法:SPFA
时间复杂度:$O(P \times C \times K)$
众所周知,$SPFA$ 算法是一个非常优秀的算法,时间复杂度为 $O(k \times m)$,$m$ 为边数,$k$ 为常数。
该题考察的为单源最短路径,枚举所有的牧场(放糖),到所有所在牛的牧场的最短距离,再取一个 最小值 即可。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 810, M = 3000, INF = 0x3f3f3f3f;
int n, P, C;
int h[N], e[M], ne[M], w[M], idx, id[N];
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 dist[M];
bool st[M];
queue <int> q;
q.push(x);
memset(dist, 0x3f, sizeof(dist));
memset(st, false, sizeof(st));
dist[x] = 0;
st[x] = true;
while (!q.empty()) {
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;
}
}
}
}
int res = 0; // 单源最短路径
for (int i = 1; i <= n; ++i) {
if (dist[id[i]] == INF) return INF;
else res += dist[id[i]];
}
return res;
}
int main()
{
cin >> n >> P >> C;
memset(h, -1, sizeof(h));
for (int i = 1; i <= n; ++i) cin >> id[i];
while (C--) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
int res = INF;
for (int i = 1; i <= P; ++i) res = min(res, spfa(i));
cout << res << endl;
return 0;
}
关于spfa,他已经 。。。🤣