Bessie, always wishing to optimize her life, has realized that she really enjoys visiting F (1 <= F <= P) favorite pastures F_i of the P (1 <= P <= 500; 1 <= F_i <= P) total pastures (conveniently
numbered 1..P) that compose Farmer John's holdings.
Bessie knows that she can navigate the C (1 <= C <= 8,000) bidirectional cowpaths (conveniently numbered 1..C) that connect various pastures to travel to any pasture on the entire farm. Associated with each path P_i is a time T_i (1 <= T_i <= 892) to traverse that path (in either direction) and two path endpoints a_i and b_i (1 <= a_i <= P; 1 <= b_i <= P).
Bessie wants to find the number of the best pasture to sleep in so that when she awakes, the average time to travel to any of her F favorite pastures is minimized.
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.
约翰拥有 P(1<=P<=500) 个牧场. 贝茜特别喜欢其中的 F 个. 所有的牧场 由 C(1 < C<=8000) 条双向路连接,第 i 路连接着 ai,bi,需要 1(1<=Ti< 892) 单 位时间来通过.
作为一只总想优化自己生活方式的奶牛,贝茜喜欢自己某一天醒来,到达所有那 F 个她喜欢的 牧场的平均需时最小. 那她前一天应该睡在哪个牧场呢?请帮助贝茜找到这个最佳牧场.
此可见,牧场 10 到所有贝茜喜欢的牧场的平均距离最小,为最佳牧场.
输入格式:
space-separated integers: a_i, b_i, and T_i
输出格式:
- 13 6 15
- 11
- 13
- 10
- 12
- 8
- 1
- 2 4 3
- 7 11 3
- 10 11 1
- 4 13 3
- 9 10 3
- 2 3 2
- 3 5 4
- 5 9 2
- 6 7 6
- 5 6 1
- 1 2 4
- 4 5 3
- 11 12 3
- 6 10 1
- 7 8 7
- 10
As the problem statement
As the problem statement.
代码:
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define N 501
- #define maxn 999999
- using namespace std;
- int n,m,t,x,y,z,s=maxn,ans,maxx,a[N],dis[N][N];
- int read()
- {
- int x=0,f=1; char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
- while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
- return x*f;
- }
- int main()
- {
- n=read(),t=read(),m=read();
- for(int i=1;i<=t;i++) a[i]=read();
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- dis[i][j]=(i!=j)*maxn;
- for(int i=1;i<=m;i++)
- x=read(),y=read(),z=read(),dis[x][y]=z,dis[y][x]=z;
- for(int k=1;k<=n;k++)
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- if (dis[i][j]>dis[i][k]+dis[k][j])
- dis[i][j]=dis[i][k]+dis[k][j];
- for(int i=1;i<=n;i++)
- {
- maxx=0;
- for(int j=1;j<=t;j++)
- maxx+=dis[i][a[j]];
- if(s>maxx) s=maxx,ans=i;
- }
- printf("%d",ans);
- }
洛谷——P2935 [USACO09JAN] 最好的地方 Best Spot
来源: http://www.bubuko.com/infodetail-2268122.html