问题：香甜的黄油
时间限制: 1 Sec 内存限制: 128 MB
提交: 117 解决: 50
[提交] [状态] [讨论版] [命题人:admin]
题目描述
农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。
农夫John很狡猾。像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。
输入
【输入格式】butter.in
第一行: 三个数：奶牛数N，牧场数P（2<=P<=800），牧场间道路数C(1<=C<=1450)。
第二行到第N+1行: 1到N头奶牛所在的牧场号。
第N+2行到第N+C+1行：每行有三个数：相连的牧场A、B，两牧场间距（1<=D<=255），当然，连接是双向的。
输出
一行 输出奶牛必须行走的最小的距离和.
样例输入
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
样例输出
8
提示
样例图形
P1 P2
@--1--@ C1
\ |\
\ | \
5 7 3
\ | \
| \ C3
C2 @--5--@
P3 P4
放在4号牧场最优
#include<bits/stdc++.h>
using namespace std;
bool enter[1000];
// 相连的牧场 两个牧场的距离 每个牧场到某点的距离
int conn[810][810],w[810][810],dis[810];
int num[810],size[810];//每个牧场的奶牛数 每个牧场有几个与它相连
int team[1688];//队列
int main()
{
int N,P,C;
while(cin>>N>>P>>C)
{
memset(size,0,sizeof(size)); //将与每点相连数置为0
//memset(w,0,sizeof(w));
//memset(enter,false,sizeof(enter));
//memset(conn,0,sizeof(conn));
memset(num,0,sizeof(num));
for(int i=1;i<=N;i++)
{
int x;
cin>>x;
num[x]++;
}
for(int i=1;i<=C;i++)
{
int x,y,z;
cin>>x>>y>>z;
w[x][y]=w[y][x]=z;
conn[x][++size[x]]=y;//数组模仿连同
conn[y][++size[y]]=x;//顺便得到连通个数size
}
int minn;//定义个最小距离
minn=0x7fffffff/3;
for(int k=1;k<=P;k++)
{
memset(enter,false,sizeof(enter));
memset(team,0,sizeof(team));
for(int i=1;i<=P;i++)
{
dis[i]=0x7fffffff;
}
int head,tail,u;//定义头尾 和标记头
dis[k]=0;team[1]=k;head=0;tail=1;enter[u]=true;
do{
head++;
head=((head-1)%1601)+1;//为什么这么写呢？
u=team[head];
enter[u]=false;//走到这个了，先出个列
for(int j=1;j<=size[u];j++)
{
if(dis[conn[u][j]]>dis[u]+w[u][conn[u][j]])
{
dis[conn[u][j]]=dis[u]+w[u][conn[u][j]];
if(!enter[conn[u][j]])
{
tail++;
tail=((tail-1)%1601)+1;
team[tail]=conn[u][j];
enter[conn[u][j]]=true;
}
}
}
}while(head!=tail);
int sum=0;//记到该点的总距离
for(int i=1;i<=P;i++)
{
if(num[i]!=0)
{
sum+=num[i]*dis[i];
}
}
minn=min(sum,minn);
}
cout<<minn<<endl;
}
return 0;
}
