Algorithm

USACO Section3.2 butter

Problem Summary

Given P pastures, C cows and their locations, and the paths connecting the pastures, choose a pasture for farmer John to put a piece of butter, making the total time that cows need to walk there minimal.

Solution

First, stimulate adjacency table with arrays to store the map.
Then, enumerate the pasture to place the butter, use SPFA to calculate the distances, and find minimal total distance.

Code

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
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
using namespace std;
const int maxp = 802;
const int maxm = 3000;
int n,p,m;
int w[maxp],dist[maxp];
int head[maxp],next_edge[maxm],en[maxm],len[maxm];
int ans=INT_MAX;
int l,r,qu[10*maxm];
bool in_qu[maxp];
void spfa(int s)
{
	memset(in_qu,0,sizeof(in_qu));
	for(int i=1;i<=p;i++)
		dist[i]=INT_MAX;
	dist[s]=0;
	qu[0]=s;
	in_qu[s]=true;
	l=0; r=1;
	int cur,u,v;
	while(l<r)
	{
		cur=qu[l];
		l++;
		u=head[cur];
		while(u>=0)
		{
			v=en[u];
			if(dist[v]>dist[cur]+len[u])
			{
				dist[v]=dist[cur]+len[u];
				if(!in_qu[v])
				{
					qu[r]=v;
					in_qu[v]=true;
					r++;
				}
			}
			u=next_edge[u];
		}
		in_qu[cur]=false;
	}
}
int get_sum()
{
	int res=0;
	for(int i=1;i<=p;i++)
	{
		if(w[i]>0 && dist[i]==INT_MAX)
			return INT_MAX;
		res+=w[i]*dist[i];
		if(res>ans) return res;
	}
	return res;
}
int main()
{
	fstream fin("butter.in",ios::in);
	fstream fout("butter.out",ios::out);
	int tmp;
	fin>>n>>p>>m;
	for(int i=0;i<n;i++)
	{
		fin>>tmp;
		w[tmp]++;
	}
	for(int i=1;i<=p;i++)
		head[i]=-1;
	int a,b,c;
	for(int i=1;i<=m;i++)
	{
		fin>>a>>b>>c;
		next_edge[i<<1]=head[a]; head[a]=i<<1; en[i<<1]=b;
		next_edge[(i<<1)+1]=head[b]; head[b]=(i<<1)+1; en[(i<<1)+1]=a;
		len[i<<1]=len[(i<<1)+1]=c;
	}
	for(int i=1;i<=p;i++)
	{
		spfa(i);
		tmp=get_sum();
		ans=tmp<ans ? tmp:ans;
	}
	fout<<ans<<endl;
	fin.close();
	fout.close();
	return 0;
}