P 6770[USACO 05 MAR]Checking an Alibiアリバイ(spfa)
14246 ワード
アリバイ
テーマゲート
問題を解く構想.
この問題は甘いバター(SPFA)とあまり差がなくて、入力と出力を変えてACになりました
ACコード
ありがとう
テーマゲート
問題を解く構想.
この問題は甘いバター(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;
}
ありがとう