USACO 3.2 Sweet Butter

This problem is essentially a shortest path problem: given a graph, find a single node in the graph (where we will put the butter) such that the combined distances from this graph node (the butter) to a set of graph nodes (the graph nodes where the cows are placed) is minimized.
The basic idea is for every node (pasture) in the graph, we calculate the shortest distances between this node and the rest of the nodes. Then for every node (pasture), we sum up the distances between itself and the pastures where cows are placed. The calculation of shortest paths between current pasture and the rest of pasture could be further optimized, as we only care about pasture with cows, so we can skip the pastures pairs where both pastures don’t have cows. But even without this optimization the code pass the test data set. The code use a slightly modified version of Dijkstra algorithm I posted earlier, otherwise there would be too much redundant computations that leads to timeout errors for large test data set.

I suspect this problem can also be solved using Bellmen-Ford or SFPA, and that would be a good exercise at some point in future…

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <map>
#include <unordered_map>
#include <climits>
#include <sstream>
#include <queue>

using namespace std;

int N /* cows */, P /* pastures */, C /* paths */;
vector<int> c2p;// [to node index, edge weight] pair.
typedef std::pair<int, int> edge;
// [node index, distance to source] pair.
typedef std::pair<int, int> element;
vector<vector<edge>> graph;
vector<int> dist;
vector<bool> visited;

class compare {
public:
    bool operator()(const element&a, const element &b) {
        return a.second > b.second;
    }
};

void dijkstra(const vector<vector<edge>> &graph, int source) {
    std::fill(visited.begin(), visited.end(), false);
    std::fill(dist.begin(), dist.end(), INT_MAX);
    dist[source] = 0;
    priority_queue<element, vector<element>, compare> pq;
    pq.emplace(make_pair(source, 0));
    while (!pq.empty()) {
        int v = pq.top().first;
        pq.pop();
        if (visited[v]) continue;
        for (auto &edge : graph[v]) {
            int u = edge.first; // vertice u that connects to v.
            int w = edge.second; // weight of edge that connects u and v.
            if (visited[u]) continue;
            if (dist[v] + w < dist[u]) {
                dist[u] = dist[v] + w;
                pq.emplace(make_pair(u, dist[u]));
            }
        }
        visited[v] = true;
    }
}

int main() {
    ifstream fin("butter.in");
    ofstream fout("butter.out");

    fin >> N >> P >> C;
    c2p = vector<int>(N + 1, 0);
    graph = vector<vector<edge>>(C + 1, vector<edge>());
    dist = vector<int>(C + 1, INT_MAX);
    visited = vector<bool>(C + 1, false);

    for (int i = 1; i < N + 1; ++i) {
        fin >> c2p[i];
    }
    for (int i = 0; i < C; ++i) {
        int s, d, w;
        fin >> s >> d >> w;
        graph[s].emplace_back(make_pair(d, w));
        graph[d].emplace_back(make_pair(s, w));
    }

    long long ret = INT_MAX;
    for (int i = 1; i <= P; ++i) {
        long long ans = 0;
        dijkstra(graph, i);
        for (int j = 1; j <= N; ++j) {
            ans += dist[c2p[j]];
        }
        ret = std::min(ret, ans);
    }

    fout << ret << endl;
    cout << ret << endl;
}