【例4-6】香甜的黄油

题目描述

农夫 John 要把糖放在某个牧场上，让所有奶牛从各自所在牧场沿最短路走过来。P（2≤P≤800）个牧场之间有 C（1≤C≤1450）条双向道路（长度 1≤D≤255），N（1≤N≤500）头奶牛分别站在某些牧场（一个牧场可以有多头牛）。选一个牧场放糖，使所有奶牛走到它的最短路程之和最小，输出这个最小值。输入第一行 N P C，接下来 N 行每行一头牛所在的牧场号，再接下来 C 行每行 A B D。样例输入 3 4 5 / 2 / 3 / 4 / 1 2 1 / 1 3 5 / 2 3 7 / 2 4 3 / 3 4 5，样例输出 8（放在 4 号牧场最优）。

思路

枚举糖放在哪个牧场，对每个候选跑一次堆优化 Dijkstra，再按每个牧场上的牛数加权求和取最小值。边权都为正、图很稀疏，单次 Dijkstra 复杂度 $O((C+P)\log P)$ ，总复杂度 $O(P(C+P)\log P)$ ；如果某个候选牧场到有牛的牧场不可达，直接跳过它。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60#!/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-30 06:22
# update_at: 2026-09-30 06:22

import sys
from collections import Counter
from heapq import heappop, heappush

UNREACHABLE = -1  # 某源点到某牧场的距离为无穷大时的占位（不可达标记）


def dijkstra(src: int, adj: list[list[tuple[int, int]]]) -> list[int]:
    """单源最短路：(src 到每个牧场的最短距离)，不可达记 UNREACHABLE。"""
    dist = [UNREACHABLE] * len(adj)
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heappop(heap)
        if d > dist[u]:     # 堆里的过期条目：已经有更短的距离定型了
            continue
        for v, w in adj[u]:
            nd = d + w
            if dist[v] == UNREACHABLE or nd < dist[v]:
                dist[v] = nd
                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)
    cows = [next(data) for _ in range(n)]           # 每头牛所在的牧场

    adj: list[list[tuple[int, int]]] = [[] for _ in range(p + 1)]  # 下标 1..p 是牧场
    for _ in range(c):
        a, b, w = next(data), next(data), next(data)
        adj[a].append((b, w))                       # 道路双向
        adj[b].append((a, w))

    head_count = Counter(cows)                      # 一个牧场可能站多头牛，按头数加权

    best = None
    for src in range(1, p + 1):
        dist = dijkstra(src, adj)
        # 有一头牛不可达，这个牧场就不合法：跳过，别让"无穷大"混进求和
        reachable = all(dist[x] != UNREACHABLE for x in head_count)
        if not reachable:
            continue
        total = sum(cnt * dist[x] for x, cnt in head_count.items())
        if best is None or total < best:
            best = total

    print(best)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106/**
 * 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-05 10:46
 * update_at: 2026-10-05 10:46
 */

// main.cpp：香甜的黄油。枚举糖放在哪个牧场，对每个候选跑一次堆优化 Dijkstra，
// 再按「该牧场上有几头牛」加权求和，取最小值。

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXN = 1005;   // 牧场数 P <= 800，留余量
const int MAXM = 3005;   // 道路数的两倍 2C <= 2900

const ll INF = 1000000000000000000LL; // 距离无穷大，求和时用不到它（不可达的候选会先被跳过）

int head[MAXN]; // head[u] 是 u 的第一条出边编号
int to[MAXM];   // to[e] 是边 e 的终点
int wei[MAXM];  // wei[e] 是边 e 的长度
int nxt[MAXM];  // nxt[e] 是 u 的下一条出边
int edge_cnt;   // 已加入的边数

ll cow_cnt[MAXN]; // cow_cnt[v] 是站在牧场 v 上的奶牛头数
ll dist[MAXN];    // dist[v] 是当前源点到 v 的最短距离

int p; // 牧场数，P <= 800
ll n;  // 奶牛数
ll c;  // 道路数

// 加一条 u 与 v 之间长 w 的无向边。
void add_edge(int u, int v, int w) {
    edge_cnt++;
    to[edge_cnt] = v;
    wei[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 堆优化 Dijkstra：求 src 到所有牧场的最短距离，写入 dist[]。
void dijkstra(int src) {
    for (int i = 1; i <= p; i++) dist[i] = INF;
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > heap;
    dist[src] = 0;
    heap.push(make_pair(0, src));
    while (!heap.empty()) {
        pair<ll, int> top = heap.top();
        heap.pop();
        ll d = top.first;
        int u = top.second;
        if (d > dist[u]) continue; // 堆里的过期条目，已经有更短的距离定型
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            ll nd = d + wei[e];
            if (nd < dist[v]) {
                dist[v] = nd;
                heap.push(make_pair(nd, v));
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> p >> c;
    for (ll i = 1; i <= n; i++) {
        ll pos;
        cin >> pos;
        cow_cnt[pos]++;
    }
    for (ll i = 1; i <= c; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        add_edge(a, b, w);
        add_edge(b, a, w);
    }

    ll best = INF;
    // 枚举糖放在哪个牧场，每个候选跑一次单源最短路。
    for (int src = 1; src <= p; src++) {
        dijkstra(src);
        ll total = 0;
        bool ok = true;
        for (int v = 1; v <= p; v++) {
            if (cow_cnt[v] == 0) continue;
            if (dist[v] == INF) { // 有牛不可达，这个牧场不合法，跳过
                ok = false;
                break;
            }
            total += cow_cnt[v] * dist[v];
        }
        if (ok && total < best) best = total;
    }

    cout << best << "\n";
    return 0;
}

【例4-6】香甜的黄油

目录

题目描述

思路

参考代码