作法: SPFA

一種最短路徑的演算法,總之就這樣,名字嚇人,其實很容易懂.

之所以不用  Dijkstra演算法  <<貌似沒辦法處理負環<< 時間大概平均都是秒以上 不穩
          Floyd-Warshall演算法 <<太慢了  雖然時間很固定...<< 好做  但是太慢了

事實上是因為  認為測資太強大  結果是輸入有誤 ... 才造就今天的SPFA

第一次寫,請多多指教!

題目是要求負環

我從 liouzhou_101 要到一個原版的題目 輸入出一模一樣

虫洞(Wormholes)
       在一个神秘岛上，有N(1 <= N <= 500)个洞口，标号1..N，它们之间有M (1 <= M <= 2500) 条通道相连。神秘的是另外还有W (1 <= W <= 200)条传说中的时间虫洞----当到达通道的另一端洞口时，竟然可以比进入的时间要早！       
       你当然想进行这样的时间之旅，希望从一个洞口s出发，经过几个通道，在比出发早些时候的时间回到洞口s。也许还能碰到自己,hehe
     根据给定的地图，请判断能否实现这样的愿望。
输入格式：
第一行：一个整数 F (1 <= F <= 5)，表示共有F组数据。（多组数据测试）每组数据：
第1行：三个整数 N  M  W      
第2至M+1行:每行三个整数 (S, E, T),表示在S与E洞口之间有一个双向通道，通过需要T(0 <= T <= 10,000) 秒。      
第M+2至M+W+1行:每行三个整数 (S, E, T),表示在S与E洞口之间有一个单向通道，从S到E可以回到之前T(0 <= T <= 10,000) 秒。
输出格式：   
    共1..F行，每行对应一组数据，如果可以实现愿望输出"YES",否则输出"NO".
输入样例(wormhole.in):

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
输出样例(wormhole.out):

NO
YES

/************************************************/

#include<stdlib.h>
#include<stdio.h>
#define MAX 1000000
short map[501][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[5000000],maptop[501]={0};
int SPFA(int S,int N,int U[],int P[])  
{  
   int Dis[501]={0},a,b,c,used[501]={0};  
   int top=-1,Flag1=0,Flag2=0;  
   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]<0) return 1;  
   Dis[S]=0;  
   for(a=0;a<=top;a++)  
      {  
         int Qp=Queue[a];  
         used[Qp]=0;  
         if(U[Qp]==1) Flag1=1;  
         if(P[Qp]==1) Flag2=1;  
         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]<0) return 1;  
         if(a>N&&(Flag1==0||Flag2==0)) return 0;  
      }  
   if(Dis[S]<0) return 1;  
   else return 0;  
}  
main()
{
  int k,N,M,W,Dis;
  scanf("%d",&k);
  while(k--)
     {
        scanf("%d %d %d",&N,&M,&W);
        int a,b,c,d,x,y;
        if(M>2500) break; /**測資輸入錯誤*/
        for(a=0;a<M;a++)
           {
             x=input(),y=input(),d=input(); 
             map[x][maptop[x]][0]=y;
             map[x][maptop[x]++][1]=d;
             map[y][maptop[y]][0]=x;
             map[y][maptop[y]++][1]=d;
           }
       int U[501]={0},P[501]={0};  
        for(a=0;a<W;a++)  
           {  
             x=input(),y=input(),d=input();  
             map[x][maptop[x]][0]=y;  
             map[x][maptop[x]++][1]=-d;  
             U[y]=1,P[x]=1;  
           } 
        int Flag=0;  
        for(a=1;a<=N&&Flag==0;a++)  
          if(U[a]==0) continue;  
          else 
             Flag=SPFA(a,N,U,P);
        if(Flag==0) printf("NO\n");
        else printf("YES\n");
        for(a=1;a<=N;a++)
           maptop[a]=0;
     }
  return 0;
}