程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> UVA558

UVA558

編輯:關於C++

UVA558 - Wormholes(BellmanFord判負環)

UVA558 - Wormholes

題目大意:
有一個教授希望利用蟲洞回到過去(還是從這個蟲洞出來就到達了過去),給你蟲洞形成的有向圖,問教授能否回到過去。

解題思路:
利用BellmanFord判負環,如果不存在負環的話,那麼最多經過N - 1次迭代就可以得到最短路,因為形成最短路最多N - 1個節點(起點不算),但是如果存在了負環,那麼就可以一直迭代,最短路會越來越小。可以利用這個性質來判斷是否存在負環。

代碼:

#include 
#include 
#include 

const int maxn = 1005;
const int maxm = 2005;

using namespace std;

struct edge {
    int u, v;
    int d;
}e[maxm];

const int INF = 0x7f7f7f7f;
int N, M;
int d[maxn];

bool BellmanFord() {
    for (int i = 0; i < N; i++)
        d[i] = i == 0 ? 0 : INF;

    d[0] = 0;
    for (int k = 0; k < N - 1; k++) 
        for (int i = 0; i < M; i++) {
            if (d[e[i].u] != INF && d[e[i].v] > d[e[i].u] + e[i].d)
                d[e[i].v] = d[e[i].u] + e[i].d;
        }

    for (int i = 0; i < M; i++)
        if (d[e[i].u] != INF && d[e[i].v] > d[e[i].u] + e[i].d) 
            return true;
    return false;
}

int main () {

    int T;
    scanf ("%d", &T);
    while (T--) {
        scanf ("%d%d", &N, &M);
        for (int i = 0; i < M; i++)
            scanf ("%d%d%d", &e[i].u, &e[i].v, &e[i].d);
        if (BellmanFord()) 
            printf ("possible\n");
        else
            printf ("not possible\n");
    }
    return 0;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved