[백준 1219] 오민식의 고민

문제

www.acmicpc.net/problem/1219

 

알고리즘

벨만포드

 

풀이

벨만포드는 은근히 생각해야할 것이 있는 주제라고 생각됩니다. 최대로 벌 수 있는 돈을 구하는 문제입니다.

 

시작지점과 도착지점이 하나씩 있는 문제는 다익스트라 또는 벨만포드를 전략으로 고려할 수 있습니다. 음의 사이클이 존재할 때, 다익스트라를 사용하지 못하므로 벨만포드를 사용하도록 합시다.

 

벨만포드의 기본적인 아이디어는 루프를 $N$번 돌며 마지막반복에서 업데이트가 일어난다면 음의 사이클이 존재한다고 판단하는 것입니다. 물론 $N$번미만 루프안에서 업데이트가 더이상 일어나지 않는다면 종료함으로써 불필요한 루프를 도는 것을 그만할 수 도 있습니다.

 

유의해야할 것 중 첫번째는 $dist$ 배열의 타입입니다. 돈과 교통비의 최댓값이 100만, N의 최댓값이 100 이여서 오버플로우가 안난다고 착각할 수 있다는 것입니다. 벨만포드는 현재까지 $k$번 루프를 돌았다면, 시작지점으로부터 $k$개의 간선을 거쳐 갈 수 있는 지점의 업데이트를 "보장"해준다는 것입니다. 운이 좋다면 도시의 배치순서에 따라 첫번째 루프에서도 도시끝까지 업데이트가 일어날 수 있습니다. 즉 오버플로우를 고려하기 위해 최댓값을 계산할 때는 $N^2*val$로 계산해야합니다. 이는 int를 초과하는 범위이므로 long long 타입을 사용해야합니다.

 

두번째는 사이클의 판별이 아니라 도달성입니다. 벨만포드의 기초문제들은  사이클의 유무를 판단하지만 이 문제에서는 만들어진 사이클에서 목적지까지 도달해야하는 것 또한 판별해야함을 잊지 맙시다. 이를 처리하기 위해 저는 $makeCy$ 큐를 통해 bfs를 수행했습니다.

 

벨만포드는 루프를 최대 $N$번돌며 그때마다 모든 간선을 검사하므로 시간복잡도는 $O(NM)$입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, s, t, m,a,b,c;
ll dist[100];
int earn[100];
bool visited[100];
vector<vector<pii>> adj;

int main() {
    FAST;
    cin >> n >> s >> t >> m;

    memset(dist, 0x3f, sizeof(dist));
    
    adj.resize(n);

    while (m--) {
        cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
    }
    rep(i, n) cin >> earn[i];

    dist[s] = -earn[s];

    queue<int> make_cy;
    bool update;
    rep(i, n) {
        update = false;

        rep(here, n) {
            if (dist[here] == INF) continue;
            for (auto [there, cost] : adj[here]) {
                cost -= earn[there];
                if (dist[here] + cost < dist[there]) {
                    update = true;
                    dist[there] = dist[here] + cost;
                    if (i == n - 1) make_cy.emplace(here);
                }
            }
        }
        if (!update) break;
    }
    bool reach = false;
    while (!make_cy.empty()) {
        auto here = make_cy.front();
        make_cy.pop();
        if (here == t) {
            reach = true;
            break;
        }
        for (auto [there, cost] : adj[here]) {
            if (!visited[there]) {
                visited[there] = true;
                make_cy.emplace(there);
            }
        }
    }

    if (dist[t] == INF) cout << "gg";
    else if (update && reach) cout << "Gee";
    else cout << -dist[t];

    return 0;
}