P 6770[USACO 05 MAR]Checking an Alibiアリバイ(spfa)

14246 ワード

アリバイ
テーマゲート
問題を解く構想.
この問題は甘いバター(SPFA)とあまり差がなくて、入力と出力を変えてACになりました
ACコード
#include
#include
#include
#include
using namespace std;
int n,p,c,m,x,y,z,o,x1,tot,head,tail,hd[100005],b[10005],v[10005],f[10005],d[10005];
struct stu
{
	int to,next,w;
}a[100005];
void add(int x,int y,int z)//    
{
	tot++;
	a[tot].to=y;
	a[tot].w=z;
	a[tot].next=hd[x];
	hd[x]=tot;
}
void spfa(int x)//spfa
{
	memset(v,0,sizeof(v));//  
	memset(d,127,sizeof(d));
	d[x]=0,v[x]=1;f[1]=x;
	head=0;tail=1;
	while(head<tail)
	{
		head++;
		x1=f[head];
		for(int j=hd[x1];j;j=a[j].next)
		 if(d[a[j].to]>d[x1]+a[j].w)//    
		  {
			d[a[j].to]=d[x1]+a[j].w;
			if(v[a[j].to]==0)
			{
				tail++;
				v[x1]=1;//  
				f[tail]=a[j].to;//  
			}
		 }
		v[x1]=0;
	} 
}
int main()
{
	scanf("%d%d%d%d",&n,&p,&c,&m);//  
	for(int i=1;i<=p;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);//  
	}	
	for(int i=1;i<=c;i++)
	{
		scanf("%d",&x);
		spfa(x);
		if(d[1]<=m)b[++o]=i;//  
	}
	cout<<o<<endl;//  
	for(int i=1;i<=o;i++)
	 cout<<b[i]<<endl;
}


ありがとう