Algoogle

Algorithm for Programming Contest

PKU 3259 Wormholes

Category: PKU Tag: bellman-ford

Wormholes

問題概要


グラフに負閉路があればYES, そうでなければNO.

解法


負閉路の検出はBellman-Fordを使うことでできる.
Bellman-Fordでは負閉路がなければ更新は|V|-1回以下のループで終わるはずなので|V|回目も試してみて更新が起これば負閉路があることになる. whileで回った回数を数えてもよい.

コード


(3259.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <map>
#include <vector>

using namespace std;

typedef pair<int,int> pii;

int N, M, W;
vector<pii> edge[512];
int dist[512];

int main(){
    int F;
    scanf("%d", &F);
    while(F--){
        scanf("%d%d%d", &N, &M, &W);
        for(int i = 0; i < N; i++) edge[i].clear();

        for(int i = 0; i < M; i++){
            int a, b, t;
            scanf("%d%d%d", &a, &b, &t);
            a--; b--;
            edge[a].push_back(pii(t,b));
            edge[b].push_back(pii(t,a));
        }
        for(int i = 0; i < W; i++){
            int a, b, t;
            scanf("%d%d%d", &a, &b, &t);
            a--; b--;
            edge[a].push_back(pii(-t,b));
        }

        bool ok = false;
        for(int i = 0; i < N; i++) dist[i] = int(1e9);
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                for(int k = 0; k < edge[j].size(); k++){
                    int to = edge[j][k].second;
                    if(dist[to] > dist[j] + edge[j][k].first){
                        dist[to] = dist[j] + edge[j][k].first;
                        if(i == N-1){
                            ok = 1;
                            goto end;
                        }
                    }
                }
    end:
        if(ok) puts("YES");
        else puts("NO");
    }
}

Comments