2008 NPSC H. 幼稚國王的行程 (SPFA版)
作法 : SPFA
/************************************************************/
#include<stdlib.h>
#include<stdio.h>
#define MAX 1000000
short map[10001][500][2];
int min(int x,int y)
{
if(x>=y) return y;
else return x;
}
int input()
{
char cha;
int x=0;
while(cha=getchar())
if(cha!=' '&&cha!='\n') break;
x=cha-48;
while(cha=getchar())
{
if(cha==' '||cha=='\n') break;
x=x*10+cha-48;
}
return x;
}
short Queue[500000],maptop[1001]={0};
int SPFA(int S,int N,int L)
{
int Dis[1001]={0},a,b,c,used[1001]={0};
int top=-1;
for(a=1;a<=N;a++)
Dis[a]=MAX;
for(a=0;a<maptop[S];a++)
{
Dis[map[S][a][0]]=min(Dis[map[S][a][0]],map[S][a][1]);
if(used[map[S][a][0]]==0)
Queue[++top]=map[S][a][0],used[map[S][a][0]]=1;
}
if(Dis[S]<=L) return 1;
for(a=0;a<=top;a++)
{
int Qp=Queue[a];
used[Qp]=0;
if(Dis[Qp]>L) continue;
for(b=0;b<maptop[Qp];b++)
if(Dis[map[Qp][b][0]]>Dis[Qp]+map[Qp][b][1])
{
Dis[map[Qp][b][0]]=Dis[Qp]+map[Qp][b][1];
if(used[map[Qp][b][0]]==0)
Queue[++top]=map[Qp][b][0],used[map[Qp][b][0]]=1;
}
if(Dis[S]<=L) return 1;
}
if(Dis[S]<=L) return 1;
else return 0;
}
main()
{
int k,N,M,Dis;
scanf("%d",&k);
while(k--)
{
scanf("%d %d %d",&N,&M,&Dis);
int a,b,c,d,x,y;
for(a=0;a<M;a++)
{
x=input(),y=input(),d=input();
if(x==y) continue;
map[x][maptop[x]][0]=y;
map[x][maptop[x]++][1]=d;
}
int ANS[1001],top=0;
for(a=1;a<=N;a++)
{
int Flag=SPFA(a,N,Dis);
if(Flag==1) ANS[top++]=a;
}
printf("%d\n",top);
for(a=0;a<top;a++)
printf("%d ",ANS[a]);
printf("\n");
for(a=1;a<=N;a++)
maptop[a]=0;
}
return 0;
}