USACO Training: Sweet Butter
USACO Training: Sweet Butter "butter"
Original Problem Statement
Sweet Butter
FJ is a sly farmer. Like Pavlov of old, he knows he can train the cows to go to a certain pasture when they hear a bell. He intends to put the sugar there and then ring the bell in the middle of the afternoon so that the evening's milking produces perfect milk.
FJ knows each cow spends her time in a given pasture (not necessarily alone). Given the pasture location of the cows and a description of the paths that connect the pastures, find the pasture in which to place the sugar cube so that the total distance walked by the cows when FJ rings the bell is minimized. FJ knows the fields are connected well enough that some solution is always possible.
PROGRAM NAME: butter
INPUT FORMAT
- Line 1: Three space-separated integers: N, the number of pastures: P (2 <= P <= 800), and the number of connecting paths: C (1 <= C <= 1,450). Cows are uniquely numbered 1..N. Pastures are uniquely numbered 1..P.
- Lines 2..N+1: Each line contains a single integer that is the pasture number in which a cow is grazing. Cow i's pasture is listed on line i+1.
- Lines N+2..N+C+1: Each line contains three space-separated integers that describe a single path that connects a pair of pastures and its length. Paths may be traversed in either direction. No pair of pastures is directly connected by more than one path. The first two integers are in the range 1..P; the third integer is in the range (1..225).
SAMPLE INPUT (file butter.in)
3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5
INPUT DETAILS
This diagram shows the connections geometrically: P2
P1 @--1--@ C1
\ |\
\ | \
5 7 3
\ | \
\| \ C3
C2 @--5--@
P3 P4
OUTPUT FORMAT
- Line 1: A single integer that is the minimum distance the cows must walk to a pasture with a sugar cube.
SAMPLE OUTPUT (file butter.out)
8 OUTPUT DETAILS: Putting the cube in pasture 4 means: cow 1 walks 3 units; cow 2 walks 5 units; cow 3 walks 0 units -- a total of 8.
How You Should Think Of This Problem
In a sparse graph of P (2 <= P <= 800) nodes connected by C (1 <= C <= 1,450) edges of variable length, N (1 <= N <= 500) cows are put on the graph. Assuming
- a cow always takes the shortest path to a target node
- and a target node that's same for all cows is chosen so that the sum of the distance from each cow to that node is minimal,
what is that sum?
The Algorithm
Clearly enough from the problem this involves shortest paths on a graph - "so that the total distance walked by the cows when FJ rings the bell is minimized". This is also a roughly sparse graph - at 800 nodes and 1450 connections. This makes Floyd-Warshall's a little slow (the time limit here is only one second), so we can use Dijkstra's with priority queues from the Standard Template Library.
This is All-Pairs Shortest Path mainly because that we need to test out every destination point possible.
My Code
/*
ID: qlstudi3
LANG: C++14
TASK: butter
*/
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int cowloc[505], tmp[805], res[805], N;
ifstream cin("butter.in");
ofstream cout("butter.out");
struct value
{
int dat, val; constexpr bool operator<( const value& rhs) const { return val > rhs.val; }
};
priority_queue<value> pq;
vector<value> elist[805];
int INF;
void dj(int st)
{
memset(tmp, 63, sizeof tmp);
INF = tmp[st];
tmp[st] = 0;
pq.push({st, 0});
while(!pq.empty())
{
value u = pq.top(); pq.pop();
if(tmp[u.dat] != u.val) continue;
for(value x:elist[u.dat])
{
int alt = u.val + x.val;
if(alt < tmp[x.dat]) { tmp[x.dat] = alt; pq.push({x.dat, alt}); }
}
}
int tot = 0;
for(int i=1; i<=N; i++) tot += tmp[cowloc[i]];
res[st] = tot;
}
int main()
{
int P, C; cin >> N >> P >> C;
for(int i=1; i<=N; i++) cin >> cowloc[i];
for(int i=1; i<=C; i++)
{
int s, e, v;
cin >> s >> e >> v;
elist[s].push_back({e, v});
elist[e].push_back({s, v});
}
for(int i=1; i<=P; i++) dj(i);
int best = 0xFFFFFF;
for(int i=1; i<=P; i++) best = (best<res[i])?best:res[i];
cout << best << endl;
}
Comments
Post a Comment