[U]3.2.6 Sweet Butter 枚举+SPFA

赤裸裸的SPFA模板题... 有点小失误，变量弄错了... 囧~

枚举集合点，A之~ 原来用的Floyd结果超时了....

/*
ID:bysen
LANG:C++
PROG:butter
*/
#include<stdio.h>
#include<queue>
#define INF 0x7FFFFFFF
#define MAXP 801
#define MAXC 1500
using namespace std;struct Edge
{int v,len;Edge *next;
}edge[MAXC<<1],*ptr[MAXP];int dist[MAXP];
int cow[MAXP];
int EdgeNum;
int N,P,C;
int ans;void addEdge( int u,int v,int len )
{Edge *p=&edge[EdgeNum++];p->v=v;p->len=len;p->next=ptr[u];ptr[u]=p;
}void init()
{ans=INF;scanf( "%d %d %d",&N,&P,&C );for( int i=1;i<=N;i++ )scanf( "%d",&cow[i] );EdgeNum=0;for( int i=1;i<=C;i++ ){int u,v,len;scanf( "%d %d %d",&u,&v,&len );addEdge( u,v,len );addEdge( v,u,len );}
}void spfa( int start )
{int dist[MAXP];queue<int> myQueue;bool inQ[MAXP]={false};for( int i=0;i<MAXP;i++ )dist[i]=INF;while( !myQueue.empty() )myQueue.pop();myQueue.push(start);inQ[start]=true;dist[start]=0;while( !myQueue.empty() ){int cur=myQueue.front();myQueue.pop();inQ[cur]=false;Edge *p=ptr[cur];while( p ){if( dist[p->v]>dist[cur]+p->len ){dist[p->v]=dist[cur]+p->len;if( inQ[p->v]==false ){inQ[p->v]=true;myQueue.push(p->v);}}p=p->next;}}int sum=0;for( int i=1;i<=N;i++ ){sum+=dist[cow[i]];//printf( "%d %d: %d\n",start,cow[i],dist[cow[i]] );}//printf( "%d\n",sum );//printf( "----------------\n" );if( ans>sum )ans=sum;
}int main()
{ freopen( "butter.in","r",stdin );freopen( "butter.out","w",stdout );init();for( int i=1;i<=P;i++ )spfa(i);//enum the startprintf( "%d\n",ans );
}