枚举每个牧场作为放糖点，从该点跑一次堆优化 Dijkstra，利用无向图最短路的对称性直接得到所有牛的路程和，取最小值。
OJ: roj
题目 ID: 2051
难度:普及
标签:图论最短路dijkstra枚举
创建: 2026-10-01 05:06
更新: 2026-10-07 13:50
前置题目
roj 1381城市路（Dijkstra）B 每枚举一个候选放糖点就跑一次与 A 完全同款的堆优化 Dijkstra（含 `if d > dist[u]: continue` 跳过过期堆记录这一步），A 只求 1 到 n 单条最短路，B 在此之上叠加无向图对称换向、按牛数加权求和与枚举全部牧场取 min。luogu P1747好奇怪的游戏A 教的『无向图最短路可反向』被 B 用作关键的换向：把每头牛到放糖点 x 反转成从 x 单源 Dijkstra 一次，从而把 N 次单终点计算压成 P 次单源计算。roj 2037usaco-2.4.3 回家B 复用 A 教的「无向图最短路对称换向」这一步：把每头牛到糖点反转成从糖点出发，从而每个候选点只需一次单源 Dijkstra，再改为加权求和取最小
题目描述
给定
思路
无向图最短路对称，从放糖点跑单源 Dijkstra 即可得到所有牛到它的距离。枚举每个牧场作为放糖点，取所有牛路程和的最小值。同一牧场多头牛用计数加权。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 10:00
# update_at: 2026-09-29 10:00
import heapq
import sys
from collections import Counter
INF = 10**30 # 不可达哨兵
def dijkstra(start: int, adj: list[list[tuple[int, int]]]) -> list[int]:
"""从 start 出发到每个牧场的最短路（堆优化 Dijkstra）。"""
dist = [INF] * len(adj)
dist[start] = 0
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: # 过期堆项：u 已被更短的路径更新过
continue
for v, w in adj[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, p, c = next(data), next(data), next(data)
# 同一牧场可能有多头牛，按头数计数，求和时乘上权重
cow_cnt = Counter(next(data) for _ in range(n))
# 邻接表，双向边
adj: list[list[tuple[int, int]]] = [[] for _ in range(p + 1)]
for _ in range(c):
a, b, w = next(data), next(data), next(data)
adj[a].append((b, w)) # 双向边
adj[b].append((a, w))
# 糖可以放在任意牧场（含没有牛的），从每个牧场各跑一次 Dijkstra，取所有牛路程和的最小值
print(min(
sum(cnt * dist[pasture] for pasture, cnt in cow_cnt.items())
for dist in (dijkstra(src, adj) for src in range(1, p + 1))
))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 10:28
* update_at: 2026-10-06 10:28
*/
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXP = 805;
const ll INF = (1LL << 60);
int n, p, c;
int cnt[MAXP]; // cnt[u] 表示牧场 u 上的牛的数量
struct Edge {
int to;
int w;
int next;
} e[MAXP * 4]; // 无向图，边数开两倍多一点
int head[MAXP], tot;
void add_edge(int u, int v, int w) {
e[++tot].to = v;
e[tot].w = w;
e[tot].next = head[u];
head[u] = tot;
}
// 从 src 出发的堆优化 Dijkstra，返回 dist 数组（下标 1..p）
void dijkstra(int src, ll dist[]) {
for (int i = 1; i <= p; ++i) dist[i] = INF;
dist[src] = 0;
// pair<距离, 节点>，priority_queue 默认大根堆，用 greater 转小根堆
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > q;
q.push(make_pair(0LL, src));
while (!q.empty()) {
pair<ll, int> cur = q.top();
q.pop();
ll d = cur.first;
int u = cur.second;
if (d > dist[u]) continue; // 过期堆项
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
ll nd = d + e[i].w;
if (nd < dist[v]) {
dist[v] = nd;
q.push(make_pair(nd, v));
}
}
}
}
int main() {
scanf("%d%d%d", &n, &p, &c);
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
++cnt[x];
}
for (int i = 1; i <= c; ++i) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
add_edge(a, b, w);
add_edge(b, a, w);
}
ll ans = INF;
ll dist[MAXP];
for (int src = 1; src <= p; ++src) {
dijkstra(src, dist);
ll sum = 0;
for (int u = 1; u <= p; ++u) {
if (cnt[u] > 0) {
sum += (ll)cnt[u] * dist[u];
}
}
if (sum < ans) ans = sum;
}
printf("%lld\n", ans);
return 0;
}