2008 NPSC H. 幼稚國王的行程
作法 : 請參考NPSC補完計畫 (感謝配合)
/*******************************************************/
#include<stdlib.h>
#include<stdio.h>
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;
}
main()
{
int k,N,M,Dis;
scanf("%d",&k);
while(k--)
{
scanf("%d %d %d",&N,&M,&Dis);
int a,b,c,d,maptop[10001]={0},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[10001],top=0;
for(a=1;a<=N;a++)
{
int D[10001]={0},V[10001]={0};
for(b=1;b<=N;b++) D[b]=1000000;
for(b=0;b<maptop[a];b++)
D[map[a][b][0]]=min(D[map[a][b][0]],map[a][b][1]);
while(1)
{
int next=0,MIN=1000000;
for(b=1;b<=N;b++)
if(V[b]==0&&D[b]<MIN) MIN=D[b],next=b;
if(next==0||MIN>Dis) break;
V[next]=1;
for(b=0;b<maptop[next];b++)
if(V[map[next][b][0]]==0&&D[next]+map[next][b][1]<D[map[next][b][0]])
D[map[next][b][0]]=D[next]+map[next][b][1];
if(D[a]<=Dis)
{ANS[top++]=a;break;}
}
}
printf("%d\n",top);
for(a=0;a<top;a++)
printf("%d ",ANS[a]);
printf("\n");
}
return 0;
}