오민식의 고민

https://www.acmicpc.net/problem/1219

1219번: 오민식의 고민

도시에서 돈을 벌고 교통수단을 이용하면

돈이 사라지므로 음수 가중치이다.

그리고, "돈을 무한히 많이 지닐 수 있는 경우"도 존재.

벨만 포드를 이용해야한다.

 

이 문제가 어려운 이유는

벨만 포드를 변형해야 하기 때문이다

 

돈을 무한히 많이 버는 케이스이므로

양수 사이클을 찾아야 한다.

 

양수 사이클이 있어도

양수 사이클을 통해 도착점까지 못 갈 수도 있다.

업데이트를 N - 1번 하는 것이 아니라,

도시 개수의 최대치를 더한 값

N + 50 만큼 돌리면서

업데이트를 수행하자.

 

도시에서 벌 수 있는 돈을

cityMoney에 저장한다.

 

타임 머신 문제는 최단거리 배열을 했는데

이 문제는 반대로 해야한다.

배열을 MIN으로 초기화 한다.

 

 

업데이트

1. 시작 도시값이 MIN, 즉 방문한 적이 없으면 

업데이트 하지 않는다.

2. 시작 도시가 양수 사이클과 연결된 도시라면

도착 도시도 양수 사이클과 연결된 도시로 업데이트

3. "도착 도시값 < 시작 도시값 + 도착 도시 수입 - 에지 가중치"

값을 업데이트

 

에지 사용 횟수가 N - 1을 넘어서도

값이 갱신된다면

양수 사이클에 연결되어 있다는 뜻이므로

MAX로 값을 갱신해준다

 

결과 출력

1. 도착 도시 값이 MIN & 도착하지 못하면 gg 출력

2. 도착 도시 값이 MAX이면 Gee 출력

3. 이외에는 도착 도시 값을 출력

 

<소스 코드>

#include <iostream>
#include <vector>
#include <limits.h>
#include <tuple>
 
using namespace std;
 
typedef tuple<int, int, int> edge;
static int n, m, sCity, eCity;
vector<long> mdistance, cityMoney;
vector<edge> edges;
 
int main()
{
    cin >> n >> sCity >> eCity >> m;
    mdistance.resize(n);
    cityMoney.resize(n);
    fill(mdistance.begin(), mdistance.end(), LONG_MIN);
 
    for (int i = 0; i < m; i++)
    {
        int start, end, price;
        cin >> start >> end >> price;
        edges.push_back(make_tuple(start, end, price));
    }
 
    for (int i = 0; i < n; i++)
    {
        cin >> cityMoney[i];
    }
    mdistance[sCity] = cityMoney[sCity];
 
    for (int i = 0; i <= n + 50; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int start = get<0>(edges[j]);
            int end = get<1>(edges[j]);
            int price = get<2>(edges[j]);
 
 
            // 1번 상황
            if (mdistance[start] == LONG_MIN)
                continue;
            // 2번 상황
            else if (mdistance[start] == LONG_MAX)
            {
                mdistance[end] = LONG_MAX;
            }
            // 3번 상황
            else if (mdistance[end] < mdistance[start] + cityMoney[end] - price)
            {
                mdistance[end] = mdistance[start] + cityMoney[end] - price;
 
                // 노드 - 1 반복 이후 갱신된다면?
                // 양수 사이클 연결 노드로 변경
                if (i >= n - 1)
                    mdistance[end] = LONG_MAX;
            }
        }
    }
 
    if (mdistance[eCity] == LONG_MIN)
        cout << "gg" << '\n';
    else if (mdistance[eCity] == LONG_MAX)
        cout << "Gee" << '\n';
    else
        cout << mdistance[eCity] << '\n';
 
}