오민식의 고민

백준 1219번: 오민식의 고민

아이디어

기본 아이디어는 골목길 문제와 비슷하다.
간선을 탈 때 빼주고, 노드에 도착했을 때 더해준다. 이 문제도 도착점까지 가는 경로에 사이클이 있는 경우에만 Gee를 출력해야 한다.
골목길 문제는 1부터 N까지 순서대로 V-1번 루프를 돌고 마지막에 한 번 더 돌린 후에 도착지가 INF인지 확인했다. 근데 얘는 시작점과 도착점이 1, N으로 정해져있지 않아서 V번의 루프로 도착지가 INF가 된다고 보장할 수 없는듯. V-1번 루프 돌려서 사이클이 있는 부분 INF로 만들고, 그 다음 V-1번 더 루프 돌려서 도착지까지 INF를 전파한다.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 50;
constexpr long long INF = 1e18;
int N, M, S, E;
vector<pair<int, long long>> adj[MAX];
vector<int> gold;
long long dist[MAX];

void solve() {
    fill(dist, dist+MAX, -INF);
    dist[S] = gold[S];
    for (int i = 0; i < 2*N; i++) {
        for (int j = 0; j < N; j++) {
            for (auto p : adj[j]) {
                long long nc = dist[j] - p.second + gold[p.first];
                if (dist[j] != -INF && dist[p.first] < nc) {
                    dist[p.first] = nc;
                    if (i >= N-1) {
                        dist[p.first] = INF;
                    }
                }
            }
        }
    }
    if (dist[E] == -INF) cout << "gg";
    else if (dist[E] == INF) cout << "Gee";
    else cout << dist[E];
    return;
}

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

    cin >> N >> S >> E >> M;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
    }
    gold = vector<int>(N);
    for (int i = 0; i < N; i++) {
        cin >> gold[i];
    }
    solve();
    return 0;
}

여담

이렇게 하는게 맞나? V-1번 돌리고 한 번 더 돌리면 될 줄 알았는데 ㅠㅠ