【题目描述】

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

【题目链接】

　　　　https://www.luogu.org/problemnew/show/P1828

【算法】

　　　　算出任意两个牧场间最短距离，枚举目的地，取最小值。floyd会超时，对每个点用spfa。

【代码】

#include
using namespace std;
struct edge{ int to,next,val; }e[];
int n,p,C,a,b,c,tot,ans=1e9,i,j;
int head[],rec[],d[][],v[];
void add(int from,int to,int val)
{
e[++tot].to=to,e[tot].val=val;
e[tot].next=head[from],head[from]=tot;
}
int main()
{
scanf("%d%d%d",&n,&p,&C);
for(i=;i<=n;i++) scanf("%d",&a),rec[a]++; for(i=;i<=C;i++) scanf("%d%d%d",&a,&b,&c),add(a,b,c),add(b,a,c); memset(d,0x3f,sizeof(d)); for(i=;i<=p;i++) { memset(v,,sizeof(v)); queue q;
d[i][i]=;
q.push(i); v[i]=;
while(q.size()) {
int x=q.front(); q.pop();
v[x]=;
for(j=head[x];j;j=e[j].next) {
int to=e[j].to,val=e[j].val;
if(d[i][to]>d[i][x]+val) {
d[i][to]=d[i][x]+val;
if(!v[to]) q.push(to),v[to]=;
}
}
}
}
for(i=;i<=p;i++) {
int tmp=;
for(j=;j<=p;j++)
tmp=tmp+d[i][j]*rec[j];
ans=min(ans,tmp);
}
printf("%d\n",ans);
return ;
}