백준 1738 골목길 C++

w에 -1을 곱해 최단 경로를 구하는 문제로 바꾼다.

벨만포드로 그래프를 순회하고 사이클이 있는 지 확인한다.

출발지에서 사이클로 갈 수 있고, 사이클에서 도착지로 갈 수 있다면 무한루프가 발생해 답은 -1이 된다.

벨만포드로 출발지에서 사이클로 갈 수 있는 지 알 수 있고,

역방향 BFS로 사이클에서 도착지로 갈 수 있는 지를 알 수 있다.

무한루프가 발생하지 않는다면 경로복원으로 경로를 찾아 출력한다.

 

#include <bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define fastio ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

vector<vector<pair<ll,ll> > > edges;
vector<vector<int> > back_edges;
int visited[101];
ll dist[101];
int where[101];

int main() {
    fastio;
    int V, E;
    cin >> V >> E;
    edges.resize(V + 1);
    back_edges.resize(V + 1);
    fill(dist, dist + V + 1, 0x7f7f7f7f);
    while (E--) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].push_back({-w, v});
        back_edges[v].push_back(u);
    }
    dist[1] = 0;
    for (int tc = 0; tc < V - 1; tc++) {
        for (int i = 1; i <= V; i++) {
            if (dist[i] == 0x7f7f7f7f) continue;
            for (const auto &[w,e]: edges[i]) {
                if (dist[e] > dist[i] + w) {
                    dist[e] = dist[i] + w;
                    where[e] = i;
                }
            }
        }
    }
    for (int i = 1; i <= V; i++) {
        if (dist[i] == 0x7f7f7f7f || dist[i] == 0x8f8f8f8f) continue;
        for (const auto &[w,e]: edges[i]) {
            if (dist[e] > dist[i] + w) {
                dist[e] = 0x8f8f8f8f;
            }
        }
    }
    if (dist[V] == 0x7f7f7f7f || dist[V] == 0x8f8f8f8f) {
        cout << -1;
        return 0;
    }
    queue<int> q;
    q.push(V);
    visited[V] = true;
    while (!q.empty()) {
        int tmp = q.front();
        q.pop();
        for (int it: back_edges[tmp]) {
            if (!visited[it]) {
                if (dist[it] == 0x8f8f8f8f) {
                    cout << -1;
                    return 0;
                }
                visited[it] = true;
                q.push(it);
            }
        }
    }
    where[1] = -1;
    vector<int> out;
    int cur = V;
    while (cur != -1) {
        out.push_back(cur);
        cur = where[cur];
    }
    for (int i = (int) out.size() - 1; i >= 0; i--) {
        cout << out[i] << " ";
    }

    return 0;
}