[USACO 2009 Jan S]Best Spot

By way of example, consider a farm laid out as the map below shows, where *'d pasture numbers are favorites. The bracketed numbers are times to traverse the cowpaths. 1*--[4]--2--[2]--3 | | [3] [4] | | 4--[3]--5--[1]---6---[6]---7--[7]--8* | | | | [3] [2] [1] [3] | | | | 13* 9--[3]--10*--[1]--11*--[3]--12* The following table shows distances for potential 'best place' of pastures 4, 5, 6, 7, 9, 10, 11, and 12: * * * * * * Favorites * * * * * * Potential Pasture Pasture Pasture Pasture Pasture Pasture Average Best Pasture 1 8 10 11 12 13 Distance ------------ -- -- -- -- -- -- ----------- 4 7 16 5 6 9 3 46/6 = 7.67 5 10 13 2 3 6 6 40/6 = 6.67 6 11 12 1 2 5 7 38/6 = 6.33 7 16 7 4 3 6 12 48/6 = 8.00 9 12 14 3 4 7 8 48/6 = 8.00 10 12 11 0 1 4 8 36/6 = 6.00 ** BEST 11 13 10 1 0 3 9 36/6 = 6.00 12 16 13 4 3 0 12 48/6 = 8.00 Thus, presuming these choices were the best ones (a program would have to check all of them somehow), the best place to sleep is pasture 10.

* Line 1: Three space-separated integers: P, F, and C
* Lines 2..F+1: Line i+2 contains a single integer: Fi
* Lines F+2..C+F+1: Line i+F+1 describes cowpath i with three space-separated integers: ai, bi, and Ti

C++(g++ 7.5.0) 解法, 执行用时: 114ms, 内存消耗: 1604K, 提交时间: 2023-03-24 14:22:12

#include <bits/stdc++.h>
using namespace std;
const int N=600,INF=0x3f3f3f3f;

int p,f,c;
int fl[N];
int mp[N][N];

void floyd()
{
	for(int k=1;k<=p;k++)
	{
		for(int i=1;i<=p;i++)
		{
			for(int j=1;j<=p;j++)
			{
				mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
			}
		}
	}
}

int main()
{
	cin >> p >> f >> c;
	for(int i=1;i<=f;i++) cin >> fl[i];
	for(int i=1;i<=p;i++)
	{
		for(int j=1;j<=p;j++)
		{
			if(i==j) mp[i][j]=0;
			else mp[i][j]=INF;
		}
	}
	
	for(int i=1;i<=c;i++)
	{
		int a,b,c; 
		cin >> a >> b >> c;
		if(mp[a][b]>c) mp[a][b]=mp[b][a]=c;
	}
	
	floyd();
	
	int ans=INF;
	int id=-1;
	for(int i=1;i<=p;i++)
	{
		int sum=0;
		for(int j=1;j<=f;j++) sum+=mp[i][fl[j]];
		
		if(sum<ans)
		{
			ans=sum;
			id=i;
		}
	}
	cout << id << endl;
	
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 144ms, 内存消耗: 1504K, 提交时间: 2019-09-21 10:26:43

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int P,F,C,a[510][510],f[510];
int main()
{
	scanf("%d%d%d",&P,&F,&C);
	for(int i=1;i<=F;++i)scanf("%d",&f[i]);
	memset(a,0x3f,sizeof(a));
	for(int i=1,u,v,w;i<=C;++i)
	{
		scanf("%d%d%d",&u,&v,&w);
		a[u][v]=a[v][u]=min(a[u][v],w);
	}
	for(int i=1;i<=P;++i)a[i][i]=0;
	for(int k=1;k<=P;++k)
		for(int i=1;i<=P;++i)
			for(int j=1;j<=P;++j)
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
	int xx=0x7fffffff,ans;
	for(int i=1;i<=P;++i)
	{
		int h=0;
		for(int j=1;j<=F;++j)
			h+=a[i][f[j]];
		if(h<xx)xx=h,ans=i;
	}
	cout<<ans;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 169ms, 内存消耗: 1504K, 提交时间: 2019-09-21 21:25:52

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
int n,p,m,v[610],f[610][610],xx,yy,zz,ans,ansv,te;
int main(){
	scanf("%d%d%d",&n,&p,&m);
	fo(i,1,p) scanf("%d",&v[i]);
	fo(i,1,n)
		fo(j,1,n)
			f[i][j]=0x3fffffff;
	fo(i,1,n) f[i][i]=0;
	fo(i,1,m){
		scanf("%d%d%d",&xx,&yy,&zz);
		if (zz<f[xx][yy]) f[xx][yy]=f[yy][xx]=zz;
	}
	fo(k,1,n)
		fo(i,1,n)
			fo(j,1,n)
				if (f[i][k]+f[k][j]<f[i][j]) f[i][j]=f[i][k]+f[k][j];
	fo(i,1,p) ans+=f[1][v[i]];
	ansv=1;
	fo(i,2,n){
		te=0;
		fo(j,1,p) te+=f[i][v[j]];
		if (te<ans){
			ans=te;
			ansv=i;
		}
	}
	printf("%d\n",ansv);
	return 0;
}

详情