USCAO3.26Sweet Butter（SPFA)

最短路复杂度估计错误以为SPFA是N*m的用了dij超时用SPFA直接跑就好了
O（k*e) K 一般为2,3；
  1 /*
  2     ID: shangca2
  3     LANG: C++
  4     TASK: butter
  5  */
  6 #include <iostream>
  7 #include<cstdio>
  8 #include<cstring>
  9 #include<algorithm>
 10 #include<stdlib.h>
 11 #include<queue>
 12 using namespace std;
 13 #define M 1500
 14 #define P 850
 15 #define N 550
 16 #define INF 0xfffffff
 17 struct node
 18 {
 19     int u,v,w,next;
 20 }ed[M<<1];
 21 int t,head[P],dis[P],a[N],n,p,c,vis[P],f[P],k[P],o[P][P];
 22 void init()
 23 {
 24     t = 0;
 25     memset(head,-1,sizeof(head));
 26 }
 27 void add(int u,int v,int w)
 28 {
 29     ed[t].u = u;
 30     ed[t].v = v;
 31     ed[t].w = w;
 32     ed[t].next = head[u];
 33     head[u] = t++;
 34 }
 35 void spfa(int st)
 36 {
 37     int i;
 38     memset(vis,0,sizeof(vis));
 39     for(i = 1; i <= p ; i++)
 40     dis[i] = INF;
 41     dis[st] = 0;
 42     queue<int>q;
 43     vis[st] = 1;
 44     q.push(st);
 45     while(!q.empty())
 46     {
 47         int u = q.front();
 48         q.pop();
 49         vis[u] = 0;
 50         for(i = head[u]; i != -1 ;i = ed[i].next)
 51         {
 52             int v = ed[i].v;
 53             if(ed[i].w+dis[u]<dis[v])
 54             {
 55                 dis[v] = ed[i].w+dis[u];
 56                 if(!vis[v])
 57                 {
 58                     vis[v] = 1;
 59                     q.push(v);
 60                 }
 61             }
 62         }
 63     }
 64     for(i = 1; i <= p ; i++)
 65     {
 66         if(o[st][i]>dis[i])
 67         {
 68             o[st][i] = dis[i];
 69             o[i][st] = dis[i];
 70         }
 71     }
 72 }
 73 int main()
 74 {
 75     freopen("butter.in","r",stdin);
 76     freopen("butter.out","w",stdout);
 77     int i,j,u,v,w;
 78     init();
 79     cin>>n>>p>>c;
 80     for(i  =0  ;i <= p ; i++)
 81         for(j = 1; j <= p ; j++)
 82         o[i][j] = INF;
 83     for(i = 1; i <= n ;i++)
 84         cin>>a[i];
 85     for(i = 1; i <= c ;i++)
 86     {
 87         scanf("%d%d%d",&u,&v,&w);
 88         add(u,v,w);
 89         add(v,u,w);
 90     }
 91     for(i = 1; i <= n ;i++)
 92     {
 93         if(!f[a[i]])
 94         {
 95             f[a[i]] = 1;
 96             spfa(a[i]);
 97         }
 98     }
 99     int minz = INF;
100     for(i = 1; i <= p ; i++)
101     {
102         int s = 0;
103         for(j = 1 ; j <= n ; j++)
104         {
105             if(a[j]!=i)
106             s+=o[a[j]][i];
107         }
108         minz = min(minz,s);
109     }
110     printf("%d
",minz);
111     return 0;
112 }
View Code