思路与算法

统计每个牧场奶牛数，枚举放糖地点，在非负无向图上运行堆优化Dijkstra，再把各地最短距离乘奶牛数求和取最小。

正确性说明

固定放糖地点时，各头奶牛独立沿最短路行走，最小总路程为频次加权距离和。Dijkstra在正权图准确求这些距离，枚举全部地点因此包含全局最优。

复杂度

O(P(C+P)log P+N)时间、O(P+C)空间，含每次距离数组初始化、图与奶牛频次初始化。

易错点

同一牧场可有多头牛，重边逐条保留。总和用64位；枚举含没有牛的地点，不能仅选已有牛的牧场。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
};

int main() {
    int n, p, c;
    cin >> n >> p >> c;
    vector<int> cnt(p);
    while (n--) {
        int x;
        cin >> x;
        cnt[x - 1]++;
    }
    vector<vector<pair<int, int>>> g(p);
    while (c--) {
        int a, b, w;
        cin >> a >> b >> w;
        --a;
        --b;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    const long long INF = 1LL << 60;
    long long ans = INF;
    for (int s = 0; s < p; s++) {
        vector<long long> d(p, INF);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                       greater<pair<long long, int>>>
            q;
        d[s] = 0;
        q.push({0, s});
        while (!q.empty()) {
            auto a = q.top();
            q.pop();
            if (a.first != d[a.second])
                continue;
            for (auto e : g[a.second])
                if (d[e.first] > a.first + e.second) {
                    d[e.first] = a.first + e.second;
                    q.push({d[e.first], e.first});
                }
        }
        long long v = 0;
        bool ok = true;
        for (int i = 0; i < p; i++)
            if (cnt[i]) {
                if (d[i] == INF) {
                    ok = false;
                    break;
                }
                v += d[i] * cnt[i];
            }
        if (ok)
            ans = min(ans, v);
    }
    cout << ans << "\n";
}