[백준] 1738번 골목길 C++

문제 출처: https://www.acmicpc.net/problem/1738

1738번: 골목길

벨만 포드를 이용하여 가중치가 가장 큰 경로를 출력해야 한다. 그러나 최적의 경로가 존재하지 않는 상황에서는 -1을 출력해야한다.

우선 경로를 알아내기 위해 값이 갱신 될 때 root[next] = j를 넣어주어 경로를 역추적 할 수 있도록 해주었다.

이 문제에서 곤란했던 부분은 어떤 상황에서 -1을 출력해야 하는지 생각하기가 어려웠다.

-1을 출력해야하는 경우들

1. 출발점에서 도착점까지 도착을 못하는경우

2. 사이클로부터 도착점에 도착할 수 있는 경우 (금품이 무한대가 되어 최적의 경로라는 것이 존재하지 않음)

--> 사이클이 존재하기만 하면 -1을 출력하도록 했었다. 사이클이 도착경로와 관계가 없는 경우에도 -1을 출력하는 문제가 있다. 따라서 사이클로 부터 도착점에 도착할 수 있는 경우는 금품이 무한대가 가능하기 때문에 -1이고

사이클로부터 도착점에 도착할 수 없는 경우 사이클 때문에 금품이 무한대가 되는 경우는 없기 때문에 경로를 출력하여 해결할 수 있다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int>P;

vector<P> adj[101];
long long INF = -123456789123;

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

    int N, M;
    cin >> N >> M;


    for (int i = 0; i < M; i++) {
        int a, b, d;
        cin >> a >> b >> d;
        adj[a].push_back(P(b, d));
    }

    long long dist[101];
    fill(dist, dist + 101, INF);

    int root[101];
    root[1] = -1;
    dist[1] = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (P p : adj[j]) {
                int next = p.first, d = p.second;
                if (dist[j] != INF && dist[next] < dist[j] + d) {
                    dist[next] = dist[j] + d;
                    root[next] = j;
                    if (i == N) { 
                        queue<int> q;
                        int visited[101] = { };
                        visited[j] = 1;
                        q.push(j);
                        while (!q.empty()) {
                            int curr = q.front(); q.pop();
                            for (P p : adj[curr]) {
                                if (visited[p.first] == 1)continue;
                                q.push(p.first);
                                visited[p.first] = 1;
                            }
                        }

                        if (visited[N]) {
                            cout << "-1";
                            return 0;
                        }
                    }
                }
            }
        }
    }
    if (dist[N] == INF) {
        cout << "-1"; return 0;
    }

   
   
    
    int prev = root[N];
    vector<int> temp;
    temp.push_back(N);
    while (true) {

        if (prev != -1) {
            temp.push_back(prev);
            prev = root[prev];
        }
        else break;
    }

    for (int i = temp.size() - 1; i >= 0; i--) {
        cout << temp[i] <<" ";
    }
        
}