USACO 3.2.6 – Sweet Butter

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct E { int b, d; };
int main() {
	freopen("butter.in", "r", stdin), freopen("butter.out", "w", stdout);
	int N, C, P, p[801] = { 0 }, best[801], INF = 10000000, min_r = INF;
	vector<E> e[801]; vector<int> cows;
	fill(e, e + 800, vector<E> ()), fill(best, best + 801, INF);
	scanf("%d %d %d", &N, &P, &C);
	for (int c, i = 0; i < N; p[c]++, cows.push_back(c), i++)
		scanf("%d", &c);
	for (int a, b, d, c = 0; c < C; c++) {
		scanf("%d %d %d", &a, &b, &d);
		e[a].push_back(E { b, d }), e[b].push_back(E { a, d });
	}
	for (int s = 1, r = 0; s <= P; fill(best, best + 801, INF), r = 0, ++s) {
		queue<E> q; q.push(E { s, best[s] = 0 });
		while (q.size()) {
			E f = q.front(); q.pop();
			for (int b = 0; b < e[f.b].size(); ++b) {
				E o = e[f.b][b];
				if (best[o.b] > o.d + best[f.b])
					q.push(E { o.b, (best[o.b] = o.d + best[f.b]) });
			}
		}
		for (int i = 0; i < cows.size(); ++i)
			r += best[cows[i]];
		min_r = r < min_r ? r : min_r;
	}
	printf("%d\n", min_r);
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: