[BOJ/C++] 1219 오민식의 고민

최단 경로가 아닌 최대 경로를 구하며 같은 도시에 여러 번 방문할 수 있습니다.

이것은 벨만-포드 알고리즘을 응용해 최대 경로를 구하고 양의 사이클의 존재 여부를 구하면 됩니다.

수정된 벨만-포드 알고리즘 방법

1. 모든 간선에 대해 최대 경로 배열 업데이트
   • 시작 노드가 방문한 적이 없으면 패스
   • 시작 노드가 양수 사이클과 연결된 도시라면 도착 노드도 양수 사이클에 연결
   • 도착 노드 < 시작 노드 + 도착 노드에서 얻는 수입 - 가중치 일때 돈을 더 많이 벌 수 있는 경로로 온 것이므로 최대 경로 배열 업데이트
2. N보다 충분히 큰 수로 1번을 반복
   • 간선을 탐색하면서 양수 사이클에서 도달할 수 있는 모든 노드를 양수 사이클에 연결하기 위함입니다.
3. 도착 노드의 최대 경로 비용 출력
   • 도착 노드가 MIN이라면 방문하지 못함
   • 도착 노드가 MAX라면 도착 노드가 양수 사이클에 연결되어 있고 도착 노드에 방문이 가능함
   • 그 외의 경우 도착 노드의 값 출력

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>

using namespace std;

using int32 = long;
using int64 = long long;

using Edge = tuple<int, int, int>;

static vector<Edge> G;
static vector<int32> dist;
static vector<int32> cityMoney;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, S, E, M;
    cin >> N >> S >> E >> M;

    dist.resize(N, LONG_MIN);
    cityMoney.resize(N);

    for(int i=0; i<M; i++)
    {
        int start, end, weight;
        cin >> start >> end >> weight;

        G.emplace_back(start, end, weight);
    }

    for(int i=0; i<N; i++)
    {
        int money;
        cin >> money;
        cityMoney[i] = money;
    }

    dist[S] = cityMoney[S];

    for(int i=0; i<N+50; i++)
    {
	    for(int j=0; j<M; j++)
	    {
            Edge edge = G[j];
            int start = get<0>(edge);
            int end = get<1>(edge);
            int weight = get<2>(edge);

            if(dist[start]==LONG_MIN)
            {
                // 시작노드가 방문하지 않았을 때
                // 해당 노드로의 경로가 없으므로 패스
                continue;
            }
            else if(dist[start]==LONG_MAX)
            {
                // 시작 노드가 양수 사이클에 포함되어 있으면
                // 도착 노드도 양수 사이클에 포함
                dist[end] = LONG_MAX;
            }
            else if(dist[end] < dist[start] + cityMoney[end] - weight)
            {
	            // 돈을 더 많이 벌 수 있는 경로가 있다면 해당 경로로 업데이트
                if(i>=N-1)
                {
                    // N-1 반복 이후 업데이트 되는 노드는 양수 사이클에 해당
                    dist[end] = LONG_MAX;
                }
                else
                {
                    dist[end] = dist[start] + cityMoney[end] - weight;
                }
            }
               
	    }
    }

    if(dist[E] == LONG_MIN)
    {
	    // 도착노드에 방문하지 못했다면
        cout << "gg";
    }
    else if(dist[E] == LONG_MAX)
    {
        // 도착노드에 방문했고 양수 사이클에 연결되어 있으면
        cout << "Gee";
    }
    else
    {
        // 그 외의 경우
        cout << dist[E];
    }

    return 0;
}