백준 #1738 골목길


BOJ #1738 - 골목길

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

# 문제 분류

최단 경로 알고리즘

풀이 접근 방법


양의 경로와 음의 경로를 바꿔준다. 경로는 양인게 부정적인 것이니까 이정도는 바로 생각해낼 수 있다. 문제는 사이클인데, 경로에 해당하지 않지만 사이클이 존재할 수 있는 가능성이 있다. 그런 경우 -1을 내주면 안되기 때문에 BFS를 돌리고 해준다. 첫 시도는 SPFA로 했는데 안되더라.. 왜지 ? 질문에도 올라가있다.


#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define fup(i, a, b, c) for (int(i) = (a); (i) <= (b); (i) += (c))
#define fdn(i, a, b, c) for (int(i) = (a); (i) >= (b); (i) -= (c))
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, M, u, v, w;

const int MAX_V = 2e5 + 10;

vii adj[MAX_V];
vi rev[MAX_V];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    fup(i, 1, M, 1) {
        cin >> u >> v >> w;

        adj[u].pb({v, -w});
        rev[v].pb(u);
    }

    queue<int> qz;
    qz.push(N);
    int visited[MAX_V] = {0};
    visited[N] = 1;

    while (!qz.empty()) {
        int curr = qz.front();
        qz.pop();

        for (int next : rev[curr]) {
            if (!visited[next]) {
                visited[next] = 1;
                qz.push(next);
            }
        }
    }

    if (!visited[N]) {
        cout << -1;
        return 0;
    }

    int prev[MAX_V];
    ll dist[MAX_V];

    fill(dist, dist + MAX_V, INF);
    dist[1] = 0;

    fup(i, 1, N, 1) {
        fup(j, 1, N, 1) {
            for (auto &p : adj[j]) {
                int next = p.X;
                int cost = p.Y;
                if (dist[j] != INF && dist[next] > dist[j] + cost) {
                    dist[next] = dist[j] + cost;
                    prev[next] = j;
                    // 방문할 수 없는 사이클의 경우 포함하지 않는다.
                    if (i == N && visited[next]) {
                        cout << -1;
                        return 0;
                    }
                }
            }
        }
    }

    if (dist[N] == INF) {
        cout << -1;
    } else {
        vi path;
        for (int i = N; i > 0; i = prev[i]) {
            path.pb(i);
        }

        reverse(path.begin(), path.end());
        for (int s : path) {
            cout << s << " ";
        }
    }
}