codeves 2038

题意：中文
思路：我们把每一个牧场作为起点，算出到每一个奶牛在的牧场的最短距离。取个min.
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int Max=803;
 4 const int INF=1e8;
 5 
 6 int n,p,c;//牛，牧场，道路//
 7 int a[Max],last[Max];
 8 struct node{
 9     int to,next,val;
10 }e[Max*400];
11 int len,vis[Max],dis[Max];
12 
13 void add(int u,int v,int x){
14     e[len].to=v;e[len].next=last[u];
15     e[len].val=x;last[u]=len++;
16 }
17 struct point
18 {
19     int val,id;
20     point(int id,int val):id(id),val(val){}
21     bool operator <(const point &x)const{
22         return val>x.val;
23     }
24 };
25 int ss;
26 void hh(int s)
27 {
28     memset(vis,0,sizeof(vis));
29     for(int i=1;i<=p;i++)
30         dis[i]=INF;
31     priority_queue<point> q;
32     q.push(point(s,0));
33     dis[s]=0;
34     while(!q.empty())
35     {
36         int cur=q.top().id;
37         int curr=q.top().val;
38         q.pop();
39         if(vis[cur]) continue;
40         vis[cur]=true;
41         for(int i=last[cur];i!=-1;i=e[i].next)
42         {
43             int id=e[i].to;
44             if(!vis[id] && curr+e[i].val < dis[id])
45             {
46                 dis[id]=curr+e[i].val;
47                 q.push(point(id,dis[id]));
48             }
49         }
50 
51     }
52     ss=0;
53     for(int i=1;i<=n;i++)
54             ss+=dis[a[i]];
55          //   cout<<ss<<endl;
56 }
57 int main()
58 {
59     int x,y,z;
60     scanf("%d%d%d",&n,&p,&c);
61     for(int i=1;i<=n;i++)
62         scanf("%d",&a[i]);
63     memset(last,-1,sizeof(last));
64     for(int i=1;i<=c;i++){
65         scanf("%d%d%d",&x,&y,&z);
66         add(x,y,z);
67         add(y,x,z);
68     }
69    int  Min=INF;
70     for(int i=1;i<=p;i++){
71         hh(i);
72         Min=min(ss,Min);
73     }
74     printf("%d
",Min);
75 }