백준 #1219 오민식의 고민


BOJ #1219 - 오민식의 고민

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

# 문제 분류

벨만 포드 알고리즘

풀이 접근 방법


도달 불가능하면 gg

음수 사이클 + 도달 가능 gee

나머지 -출력


#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define fup(i, a, b, c) for (ll(i) = (a); (i) <= (b); (i) += (c))
#define fdn(i, a, b, c) for (ll(i) = (a); (i) >= (b); (i) -= (c))
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<ll, ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const ll stMAX = 1 << 18;
const ll INF = 1e9;
ll N, Start, Dest, M, city[200];
vii adj[200];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> Start >> Dest >> M;
    fup(i, 1, M, 1) {
        ll s, e, c;
        cin >> s >> e >> c;

        adj[s].pb({e, c});
    }

    fup(i, 1, N, 1) {
        cin >> city[i - 1];
    }

    ll dist[200];
    bool flag = false;
    fill(dist, dist + 200, INF);
    dist[Start] = -city[Start];
    vi neg;

    fup(i, 0, N - 1, 1) {
        fup(j, 0, N - 1, 1) {
            for (auto &p : adj[j]) {
                ll next = p.first;
                ll cost = p.second;

                if (dist[j] != INF && dist[next] > dist[j] + cost - city[next]) {
                    dist[next] = dist[j] + cost - city[next];
                    if (i == N - 1) {
                        flag = true;
                        neg.pb(j);
                    }
                }
            }
        }
    }

    if (dist[Dest] == INF) {
        cout << "gg";
        return 0;
    }

    if (flag) {
        bool negReach = false;
        for (ll p : neg) {
            ll visited[200] = {0};
            visited[p] = 1;

            queue<ll> q;
            q.push(p);

            while (!q.empty()) {
                ll curr = q.front();
                q.pop();

                for (pi nv : adj[curr]) {
                    ll next = nv.first;
                    if (!visited[next]) {
                        visited[next] = 1;
                        q.push(next);
                    }
                }
            }

            if (visited[Dest]) {
                negReach = true;
            }
        }

        if (negReach) {
            cout << "Gee";
            return 0;
        }
    }
    cout << -dist[Dest];
}