[BOJ-1219]오민식의 고민

[문제요약]

각 노드에는 얻을 수 있는 수익만큼 소지금이 늘어난다.

간선을 이동시에는 간선에 있는 값 만큼 소지금이 줄어든다.

노드의 개수 시작노드 도착노드 간선의 개수 가 주어질 때 

1. 도달할 수 없다면 "gg" 를 출력.
2. 도달할 수 있다면 도착노드에서 얻을 수 있는 최대 소지금을 출력.
3. 도달할 수 있을 때, 무한히 돈을 벌 수 있다면 "Gee"를 출력.
   

[문제풀이]

벨만포드(Bellman-ford) 알고리즘을 사용한다. 

시작위치에서 도달할 수 없는 것은 BFS탐색을 하며 확인이 가능하다.

벨만포드 알고리즘을 사용하면, 음의 사이클을 구할 수 있지만, 그 위치에서 도달위치로 갈 수 있어야 "Gee"를 출력할 수 있다. 이 부분을 계속 생각을 못해서 6달간 못풀고 거의 20번 넘게 틀렸던 것 같다...

[C++ Source Code]

#include<cstdio>
#include<vector>
#include<queue>
#include<memory.h>
#include<limits.h>
using namespace std;
 
typedef long long lld;
struct info {
    int next;
    lld cost;
    info(int inext, lld icost) :next(inext), cost(icost) {}
};
 
typedef vector<info> edge_info;
const int MAX_NODE = 111;
const lld MINUS_INF = LLONG_MIN;
edge_info edges[MAX_NODE];
lld city[MAX_NODE];
lld earn[MAX_NODE];
 
int main() {
    int n, s, e, m;
    scanf("%d%d%d%d", &n, &s, &e, &m);
 
    for (int i = 0; i < m; i++) {
        int u, v;
        lld w;
        scanf("%d%d%lld", &u, &v, &w);
        edges[u].push_back(info(v, w));
    }
    for (int i = 0; i < n; i++) {
        scanf("%lld", &earn[i]);
    } // input end
 
 
    vector<int> visited_node;
    visited_node.push_back(s);
 
    int visit[MAX_NODE];
    memset(visit, 0, sizeof(visit));
 
    queue<int> Q;
    Q.push(s);
 
    visit[s] = 1;
    while (!Q.empty()) {
        int here = Q.front();
        Q.pop();
        for (auto edge : edges[here]) {
            int there = edge.next;
            if (visit[there]) continue;
            visit[there] = true;
            Q.push(there);
            visited_node.push_back(there);
        }
    } // 1. Create visited node sequence 
 
    if (!visit[e]) {
        puts("gg");
        return 0;
    } // 2. result condition : impossible
 
    for (int i = 0; i < n; i++) city[i] = MINUS_INF; // init
    city[s] = earn[s];
 
    bool updated;
    int negative_cycle_node;
    memset(visit, 0, sizeof(visit));
    for (int iter = 0; iter < n; iter++) {
        updated = false;
        for (int here = 0; here < n; here++) {
            if (city[here] == MINUS_INF) continue;
            for (auto edge : edges[here]) {
                int there = edge.next;
                lld tcost = -edge.cost + city[here] + earn[there];
                if (city[there] < tcost) {
                    city[there] = tcost;
                    updated = true;
                    if (iter == n - 1) {
                        Q.push(there);
                        visit[there] = 1;
                    }                    
                }
            }
        }
        if (!updated) break;
    }
    
    if (updated) {
        while (!Q.empty()){
            int here = Q.front();
            Q.pop();
            for (auto edge : edges[here]) {
                if (visit[edge.next]) continue;
                visit[edge.next] = 1;
                Q.push(edge.next);
            }
        }
    } 
 
    if (updated && visit[e]) puts("Gee");
    else printf("%lld\n", city[e]);
 
    return 0;
}
 
// 16% WA 
/*
4 0 1 4
0 1 3
0 2 0
2 3 0
3 2 0
0 0 0 1
*/
// 17% WA