摸索C語言

2009-11-25 17:54:56來源不明

老Z的题

留言 1 收藏 0 推薦 0

作法: SPFA

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

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

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

第一次寫,請多多指教!

Dijkstra演算法

A*演算法

Bellman-Ford演算法

SPFA演算法 (Bellman-Ford演算法的改進版本)

Floyd-Warshall演算法

Johnson演算法

Bi-Direction BFS演算法

題目是要求負環

我從 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;
}