程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 3259 Wormholes (BELLman—FOrd算法)(鄰接矩陣表示)

poj 3259 Wormholes (BELLman—FOrd算法)(鄰接矩陣表示)

編輯:關於C++

 

之前一開始 ,沒做出來,擱置了好幾天才看見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;

}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved