poj 3259 Wormholes （BELLman—FOrd算法）（鄰接矩陣表示）

poj 3259 Wormholes （BELLman—FOrd算法）（鄰接矩陣表示）

之前一開始 ，沒做出來，擱置了好幾天才看見bug所在。所以今天a掉了 ，把代碼貼出來，這個使用鄰接矩陣表示的 ，下一篇用鄰接表可以提高效率。

#include
#include
#include
#include
using namespace std;
const int INF=600;
int G[INF][INF];
int inq[INF];
int res[INF];
int dict[INF];
int n,m,w;

bool spfa(int x)
{
    queuecnt;
    memset(dict,0,sizeof(dict));
    cnt.push(x);
    memset(res,0x1f,sizeof(res));
    memset(inq,0,sizeof(inq));
    res[x]=0;
    dict[x]++;
    while(!cnt.empty())
    {
        int cur=cnt.front();
        cnt.pop();
        inq[cur]=0;
        for(int i=1; i<=n; i++)
        {
            if(res[i]>res[cur]+G[cur][i])
            {
                res[i]=res[cur]+G[cur][i];
                if(!inq[i])
                {
                    cnt.push(i);
                    inq[i]=1;
                    if(++dict[i]>=n)
                        return 1;
                }
            }
        }
    }
    return 0;
}

int main()
{
    int s,e,t;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>w;
        memset(G,0x1f,sizeof(G));
        int k;
        for(int i=0; i>s>>e>>t;
            G[s][e]=G[e][s]= G[e][s]>t? t:G[s][e];
            k=s;
        }
        for(int j=0; j>s>>e>>t;
            G[s][e]=G[s][e]>-t?-t : G[s][e];

        }
        printf(%s
,spfa(1)?YES:NO);
    }
    return 0;

}