[1219] 오민식의 고민

https://www.acmicpc.net/problem/1219

1219번: 오민식의 고민

<문제>

간선의 가중치의 의미를 잘 생각해보면, 교통수단의 가격이 해당 도시에서 벌 수 있는 돈보다 더 적은 경우에는

음수간선이 만들어지게 되므로 벨만포드를 사용해야만 한다.

 

"gg"를 출력해야하는 조건은 간단하다. 벨만포드를 돌린 이후에 dst[e]가 INF인지를 확인해도 되며,

단순히 dfs나 bfs를 돌려도 된다.

"Gee"의 조건은 더 생각해봐야 할 것이 있는데, 음수 사이클이 존재함은 물론, 음수 사이클이 발생하였을때

(해당 사이클의 노드)에서 (도착 도시)까지 갈 수 있는지를 한번 더 체크해주면 된다.

 

사실 벨만포드에 dfs/bfs를 더한것 뿐이고, V<=50이라 시간이나 메모리도 상당히 넉넉한데,

"Gee"를 출력해야 하는 조건을 놓치기 쉬운 문제였다.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using pi = pair<ll, ll>;

const ll INF = (ll)-1e13;

ll n, s, e, m, ans, dst[55], a[55];

vector<pi> adj[55];

queue<int> q;

bool vst[55], cycleFlag = false;

bool f(void) {

    while (!q.empty()) {

        int cur = q.front();

        q.pop();

        for (auto nxt : adj[cur]) {

            if (vst[nxt.first] == false) {

                vst[nxt.first] = true;

                q.push(nxt.first);

            }

        }

    }

    return vst[e] == true;

}

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n >> s >> e >> m;

    ll i, j;

    for (i = 0; i < m; i++) {

        ll A, B, C;

        cin >> A >> B >> C;

        adj[A].push_back({B, C});

    }

    for (i = 0; i < n; i++) cin >> a[i];

    fill(&dst[0], &dst[53], INF);

    dst[s] = a[s];

    for (i = 0; i < n; i++) {

        for (j = 0; j < n; j++) {

            if (dst[j] == INF) continue;

            for (auto& x : adj[j]) {

                ll nIdx = x.first;

                ll nCost = dst[j] + a[nIdx] - x.second;

                if (dst[nIdx] < nCost) {

                    dst[nIdx] = nCost;

                    if (i == n - 1) {

                        cycleFlag = true;

                        vst[j] = true;

                        q.push(j);

                    }

                }

            }

        }

    }

    if (dst[e] == INF) {

        cout << "gg";

        return 0;

    }

    if (cycleFlag == true && f()) {

        cout << "Gee";

        return 0;

    }

    cout << dst[e];

    return 0;

}