USACO Section 3.2 Sweet Butter - 还是SPFA好使..

这道题就是先找出两两间的最短路...然后扫描所有点找出到达所要求点距离和最小的..

开始我用的Floyd..超时很严重阿.然后想写Bellman-Ford...但发现效率也不高...那就果断SPFA了...果然高效...水过...

Progarm:

/* ID: zzyzzy12 LANG: C++ TASK: butter */ #include<iostream> #include<istream> #include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<algorithm> #include<queue> #define oo 1000000000 #define ll long long using namespace std; struct node { int x,y,w,next; }line[3000]; int arc[810][810],n,p,c,s[810],_link[810]; queue<int> myqueue; int SPFA() { int i,j,m,h,g,k=oo; bool had[810]; memset(had,false,sizeof(had)); for (i=1;i<=p;i++) { while (!myqueue.empty()) myqueue.pop(); myqueue.push(i); while (!myqueue.empty()) { h=myqueue.front(); myqueue.pop(); had[h]=false; g=_link[h]; while (g) { if (arc[i][line[g].y]>arc[i][line[g].x]+line[g].w) { arc[i][line[g].y]=arc[i][line[g].x]+line[g].w; if (!had[line[g].y]) { myqueue.push(line[g].y); had[line[g].y]=true; } } g=line[g].next; } } m=0; for (j=1;j<=n;j++) if (arc[i][s[j]]!=oo) m+=arc[i][s[j]]; else goto A; if (m<k) k=m; A: ; } return k; } int main() { freopen("butter.in","r",stdin); freopen("butter.out","w",stdout); scanf("%d%d%d",&n,&p,&c); int i,j,k,m; for (i=1;i<=p;i++) for (j=1;j<=p;j++) arc[i][j]=oo; for (i=1;i<=p;i++) arc[i][i]=0; memset(_link,0,sizeof(_link)); for (i=1;i<=n;i++) scanf("%d",&s[i]); for (i=1;i<=c;i++) { scanf("%d%d%d",&j,&k,&m); line[i*2-1].x=j; line[i*2-1].y=k; line[i*2-1].w=m; line[i*2-1].next=_link[j]; _link[j]=i*2-1; line[i*2].x=k; line[i*2].y=j; line[i*2].w=m; line[i*2].next=_link[k]; _link[k]=i*2; } printf("%d\n",SPFA()); return 0; }