【UOJ 484】香甜的黄油

 

【题目描述】：

农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。

农夫John很狡猾。像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

【输入描述】：

第一行: 三个数：奶牛数N，牧场数P，牧场间道路数C。

第二行到第N+1行: 1到N头奶牛所在的牧场号。

第N+2行到第N+C+1行：每行有三个数：相连的牧场A、B，两牧场间距，当然，连接是双向的。

【输出描述】：

一行 输出奶牛必须行走的最小的距离和。

【样例输入】：

3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5

【样例输出】：

8

【样例说明】：

P2 P1 @--1--@ C1 \ |\ \ | \ 5 7 3 \ | \ \| \ C3 C2 @--5--@ P3 P4

【时间限制、数据范围及描述】：

时间：1s 空间：128M

2<=P<=800; 1<=C<=1450; 1<=D<=255;

题解：最后一篇博客！！感动，18完层了！前两天考试题，板子了

80分代码如下：Floyd

#include<bits/stdc++.h> #include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; const int oo=0x3f3f3f3f; int n,p,c,a[1500][1500],f[1500]; int x,y,z,ans=oo; inline int get(){ int f=1; char c=getchar(); int res=0; while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); } while (c>='0'&&c<='9'){ res=(res<<3)+(res<<1)+c-'0'; c=getchar(); } return res*f; } int main(){ //scanf("%d %d %d",&n,&p,&c); n=get(); p=get(); c=get(); memset(a,oo,sizeof(a)); for(int i=1;i<=p;i++) a[i][i]=0; for(int i=1;i<=n;i++) f[i]=get(); for(int i=1;i<=c;i++){ //scanf("%d %d %d",&x,&y,&z); x=get();y=get();z=get(); a[x][y]=z; a[y][x]=z; } 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]); for(int i=1;i<=p;i++){ int num=0; for(int j=

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11186063.html