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

79愛的鼓勵 1訂閱站台

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