摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 請參考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;
}