[BOJ] 오민식의 고민

[BOJ] 오민식의 고민

Problem URL : 오민식의 고민

#include <vector>
#include <queue>
#include <iostream>
#define p pair<int,int>
#define INF 987654321

using namespace std;

vector<p> edge[101];
long long dist[101];
int n, m, start, finish, earning[101];
bool visited[100] = { false, };
queue<int> negativeCycleNode;

void bellman() {
    for (int i = 1; i <= n - 1; i++) {
        bool updated = false;
        for (int node = 0; node < n; node++) {
            for (int nth = 0; nth < edge[node].size(); nth++) {
                if (dist[node] == INF) continue;
                int to = edge[node][nth].first;
                int cost = edge[node][nth].second;
                // 돈을 버는 것은 비용이 드는 개념의 -로 생각할 수 있다.
                // 그래서 earning에 -를 붙여주자
                long long newDist = dist[node] + cost - earning[to];
                if (dist[to] > newDist) {
                    dist[to] = newDist;
                    updated = true;
                }
            }
        }
        if (!updated) {
            // 갱신이 안되었으면 조기종료
            return;
        }
    }

    // 음수 싸이클 확인 과정
    for (int node = 0; node < n; node++) {
        for (int nth = 0; nth < edge[node].size(); nth++) {
            if (dist[node] == INF) continue;
            int to = edge[node][nth].first;
            int cost = edge[node][nth].second;
            long long newDist = dist[node] + cost - earning[to];
            if (dist[to] > newDist) {
                dist[to] = newDist;
                visited[node] = true; 
                // 음수 싸이클 노드를 모아준다.
                negativeCycleNode.push(node);
            }
        }
    }

}

// 음수 싸이클 노드로부터 finish(도착점)까지 이동할 수 있는지 확인
bool isGee() {
    while (!negativeCycleNode.empty()) {
        int cur = negativeCycleNode.front();
        negativeCycleNode.pop();

        for (int i = 0; i < edge[cur].size(); i++) {
            int next = edge[cur][i].first;
            if (visited[next]) continue;
            visited[next] = true;
            negativeCycleNode.push(next);
        }
        if (visited[finish]) {
            return true;
        }
    }
    return false;
}

int main() {
    int from, to, cost;
    scanf("%d %d %d %d", &n, &start, &finish, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &from, &to, &cost);
        edge[from].push_back({ to, cost });
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", earning + i);
    }
    fill(dist, dist + n, INF);
    dist[start] = -earning[start];

    bellman();

    if (dist[finish] == INF) {
        printf("gg\n");
    } else {
        if (isGee()) {
            printf("Gee\n");
        } else {
            printf("%lld\n", -dist[finish]);
        }
    }

    return 0;
}

Comments

벨만 포드 알고리즘
각 노드에서 돈을 버는 개념을 -해준 후, 간선에서 드는 비용에 더해주는 게 포인트
벨만 포드 조기 종료 조건과 음수 싸이클 확인 과정을 잘 기억해두자