Hướng giải của Nghịch lý thời gian

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Phát hiện chu trình âm có tính chất liên thông. Ta cần kiểm tra xem có chu trình âm nào có thể đạt tới được từ đỉnh nguồn \(S\) mà từ chu trình đó ta có thể đi tiếp tới đích \(T\) hay không. Đầu tiên chạy Bellman-Ford \(N-1\) lần để tính khoảng cách. Sau đó ở lần lặp thứ \(N\), bất kỳ đỉnh nào vẫn bị thư giãn (giảm khoảng cách) là các đỉnh bị ảnh hưởng bởi chu trình âm. Ta đẩy các đỉnh này vào một hàng đợi và chạy BFS/DFS thông thường trên đồ thị để kiểm tra xem có thể tới đích \(T\) hay không.

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

struct Edge {
    int u, v;
    long long w;
};

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

    int n, m, s, t;
    if (!(cin >> n >> m >> s >> t)) return 0;

    vector<Edge> edges(m);
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        adj[edges[i].u].push_back(edges[i].v);
    }

    vector<long long> dist(n + 1, INF);
    dist[s] = 0;

    for (int i = 1; i < n; i++) {
        for (const auto& e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }

    vector<int> in_neg_cycle;
    for (const auto& e : edges) {
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
            in_neg_cycle.push_back(e.v);
        }
    }

    vector<bool> visited(n + 1, false);
    queue<int> q;
    for (int u : in_neg_cycle) {
        if (!visited[u]) {
            visited[u] = true;
            q.push(u);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }

    if (visited[t]) {
        cout << "INFINITY\n";
    } else if (dist[t] == INF) {
        cout << "unreachable\n";
    } else {
        cout << dist[t] << "\n";
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.