题目
传送门
P1828 [USACO3.2] 香甜的黄油 Sweet Butter - 洛谷 | 计算机科学教育新生态
https://www.luogu.com.cn/problem/P1828
思路
以每头奶牛所在的牧场为起点，求得到全图各个点的最短距离
再枚举全图所有点，计算从所有起点到某点的距离之和，取最小值即可
可以循环依次跑 Dijkstra，也可跑一遍 Floyd
后者更好写，但前者更快，实测前者时间效率约为后者的 6 倍
细节
每个牧场可能有不止一头奶牛，最后结算的距离需要乘上每个牧场的奶牛的头数
代码
堆优化Dijkstra
#include <map>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
typedef pair<int, int> PII;
constexpr int C = 501, N = 801;
vector<PII> to[N];
map<int, int> cow;
int n, m, c, x, dist[C][N], cnt, ans = 1E9; //dist 记录不同起点跑出来的 Dijkstra 的结果
void Dijkstra(int start, int num) //起点，奶牛头数
{priority_queue<PII, vector<PII>, greater<PII>> q;bool mk[N]{};dist[cnt][start] = 0;q.emplace(0, start);while (q.size()) //真是模模又板板啊{int x = q.top().second;q.pop();if (mk[x]) continue;mk[x] = true;for (auto& z : to[x]){int X = z.first, w = z.second;if (dist[cnt][x] + w < dist[cnt][X]){dist[cnt][X] = dist[cnt][x] + w;q.emplace(dist[cnt][X], X);}}}for (int i = 1; i <= n; ++i) dist[cnt][i] *= num; //结果要乘以奶牛头数++cnt; //用 cnt 分配每轮 Dijkstra 用到的 dist 的第一个下标，最后 cnt = cow.size()
}
int main()
{ios::sync_with_stdio(false); cin.tie(0);memset(dist, 0x3f, sizeof(dist)); //别忘了初始化cin >> c >> n >> m;while (c--) cin >> x, ++cow[x]; //first 存奶牛所在的牧场，second 存该牧场有多少头奶牛while (m--){int x, y, w;cin >> x >> y >> w;to[x].emplace_back(y, w);to[y].emplace_back(x, w);}for (auto& z : cow) Dijkstra(z.first, z.second); //循环跑 Dijkstrafor (int i = 1; i <= n; ++i){int sum = 0;for (int j = 0; j < cnt; ++j){if (dist[j][i] == dist[0][0]) { sum = 1E9; break; } //可能有无法到达的牧场，遇到直接终止sum += dist[j][i];}ans = min(ans, sum);}cout << ans;return 0;
}Floyd
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
constexpr int N = 801;
map<int, int> cow;
int n, m, c, x, dist[N][N], ans = 1E9;
int main()
{ios::sync_with_stdio(0); cin.tie(0);memset(dist, 0x3f, sizeof(dist));cin >> c >> n >> m;while (c--) cin >> x, ++cow[x]; //first 存奶牛所在的牧场，second 存该牧场有多少头奶牛for (int i = 1; i <= n; ++i) dist[i][i] = 0; //自己到自己的距离是 0，别忘了while (m--){int x, y, w;cin >> x >> y >> w;dist[x][y] = dist[y][x] = min(dist[x][y], w); //去重边}for (int k = 1; k <= n; ++k) //真是模模又板板啊for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);for (int i = 1; i <= n; ++i){int sum = 0;for (auto& z : cow){if (dist[z.first][i] == dist[0][0]) { sum = 1E9; break; } //无法到达的点sum += dist[z.first][i] * z.second; //别忘了乘以奶牛头数}ans = min(ans, sum);}cout << ans;return 0;
}
