[Bellman-Ford]BOJ 1219_오민식의 고민

문제 링크 : www.acmicpc.net/problem/1219

1219번: 오민식의 고민

벨만-포드 알고리즘에 대한 전반적인 이해가 필요한 문제이다.

이 문제를 막힘없이 해결할 수 있다면 벨만-포드를 잘 이해했다고 볼 수 있을 것이다.

 

기본적으로는 (도로를 지나며 사용하는 비용 - 도시에 도착해서 벌 수 있는 비용) 을 간선의 비용으로 두는

그래프에 대해 벨만-포드 알고리즘을 적용해 문제를 풀면 된다.

(즉 수익의 최대화는 가중치의 최소화가 된다.)

하지만 문제의 조건에서

gg는 오민식이 해당 도시에 도착할 수 없을 때 출력하고,

Gee는 오민식이 도착 도시에 도착했을 때 돈을 무한히 갖고 있다면 출력한다.

 

즉 벨만-포드 알고리즘을 통해 음의 사이클을 확인했다고 해서 바로 Gee를 출력하게 되면 오답이 된다.

음의 사이클이 발생한 정점을 오민식이 출발점에서 도달할 수 있는 경우에만 Gee를 출력해야 한다.

본 풀이에서는 음의 사이클이 발생한 경우 해당 노드를 따로 기록해둔 후,

BFS를 통해 음의 사이클이 발생한 노드가 도달 가능한 노드인지 확인하고 최종 답을 출력한다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
 
#define INF 9999999999999999
 
using namespace std;
typedef pair<int, int> p;
vector<p> adj[101];
long long dist[101];
int n, m, start, finish, earn[101];
bool visit[100] = { false, };
queue<int> cyclenode;
int cyclestart;
 
void bellman() {
    for (int i = 0; i < n * 2; i++) {
        for (int j = 0; j < n; j++) {
            //인접 리스트 참조
            for (int k = 0; k < adj[j].size(); k++) {
                p temp = adj[j][k];
                //각 도시에서 벌 수 있는 돈을 음의 가중치로 둔다.
                long long newdist = dist[j] + temp.second - earn[temp.first];
                if (dist[j] != INF && dist[temp.first] > newdist) {
                    dist[temp.first] = newdist;
                    if (i == n - 1) { visit[j] = true; cyclenode.push(j); }
                }
            }
        }
    }
}
 
bool isGee() {
    //bfs로 finish에 도달가능한지 판단
 
    while (!cyclenode.empty()) {
        int cur = cyclenode.front();
        cyclenode.pop();
 
        for (int i = 0; i < adj[cur].size(); i++) {
            int next = adj[cur][i].first;
            if (visit[next]) continue;
            visit[next] = true;
            cyclenode.push(next);
        }
    }
 
    if (visit[finish]) return true;
    return false;
}
 
void init() {
    int u, v, w;
    cin >> n >> start >> finish >> m;
 
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
    }
 
    for (int i = 0; i < n; i++) cin >> earn[i];
 
    fill(dist, dist + n, INF);
    dist[start] = -earn[start];
}
 
int main() {
    init();
 
    bellman();
 
    if (dist[finish] == INF) printf("gg\n");
    else {
        if (isGee()) printf("Gee\n");
        else printf("%lld\n", -dist[finish]);
    }
 
    return 0;
}
 

 

dist 배열의 자료형이 long long임에 주의하자.