[USACO]Sweet Butter 多种解法

 1 /*
 2 ID: dream.y1
 3 PROG: butter
 4 LANG: C++
 5 */
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <queue>
 9 #include <vector>
10 #include <climits>
11 using namespace std;
12 const int Ni = 1000;
13 const int INF = 1<<27;
14 struct node{
15     int x,d;
16     node(){}
17     node(int a,int b){x=a;d=b;}
18     bool operator < (const node & a) const
19     {
20         if(d==a.d) return x<a.x;
21         else return d > a.d;
22     }
23 };
24 vector<node> eg[Ni];
25 int dis[Ni],n;
26 void Dijkstra(int s)
27 {
28     int i;
29     for(i=0;i<=n;i++) dis[i]=INF;
30     dis[s]=0;
31     priority_queue<node> q;
32     q.push(node(s,dis[s]));
33     while(!q.empty())
34     {
35         node x=q.top();q.pop();
36         for(i=0;i<eg[x.x].size();i++)
37         {
38             node y=eg[x.x][i];
39             if(dis[y.x]>x.d+y.d)
40             {
41                 dis[y.x]=x.d+y.d;
42                 q.push(node(y.x,dis[y.x]));
43             }
44         }
45     }
46 }
47 int ans[1000];
48 int main()
49 {
50     freopen("butter.in","r",stdin);
51     freopen("butter.out","w",stdout);
52     int a,b,d,p,c;
53     scanf("%d %d %d",&p,&n,&c);
54     for(int i = 1;i <= p; i ++)
55         scanf("%d",&ans[i]);
56     for(int i=0;i<= n;i++) eg[i].clear();
57     while(c--)
58     {
59         scanf("%d%d%d",&a,&b,&d);
60         eg[a].push_back(node(b,d));
61         eg[b].push_back(node(a,d));
62     }
63     int min = INT_MAX;
64     for(int i = 1;i <= n ;i ++ )
65     {    
66       Dijkstra(i);
67       int tsum = 0  ;
68         for(int j = 1;j <= p;j ++)
69           tsum += dis[ans[j]];
70        if(tsum < min)
71            min = tsum ; 
72     }
73     printf("%d\n",min);
74     return 0;
75 }