Chương trình C++ kiểm tra chuyến đi vòng tròn từ mỗi thành phố

Mô tả bài toán

n thành phố, đường đơn hướng có thời gian. Với mỗi thành phố, kiểm tra có chu trình quay về thành phố đó không. Nếu có in thời gian ngắn nhất, ngược lại -1.

Ví dụ

n=4,m=4, roads={{1,2,5},{2,3,8},{3,4,7},{4,1,6}}. Đầu ra: 26 26 26 26.

Thuật toán (Dijkstra từ mỗi đỉnh tìm chu trình)

1. Với mỗi đỉnh i, chạy Dijkstra tìm đường đi ngắn nhất từ i về i (khởi tạo dst[i]=0 vào heap).
2. Khi pop đỉnh curr với khoảng cách dt: nếu và 0 → tìm thấy chu trình, dừng.
3. Nếu không tìm thấy → -1.

Đoạn mã C++

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

void solve(int n,int m,vector<tuple<int,int,int>> roads){
    vector<vector<pair<int,int>>> graph(n);
    for(auto [x,y,z]:roads){
        x--; y--;
        graph[x].emplace_back(y,z);
    }
    for(int i=0;i0){ dst[i]=dt; break; }
            if(dst[curr]!=-1) continue;
            dst[curr]=dt;
            for(auto [tp,cst]:graph[curr])
                pq.emplace(dt+cst,tp);
        }
        if(dst[i]==0) dst[i]=-1;
        cout << dst[i] << (i+1==n?'\n':' ');
    }
}

int main(){
    int n=4,m=4;
    vector<tuple<int,int,int>> roads=
        {{1,2,5},{2,3,8},{3,4,7},{4,1,6}};
    solve(n,m,roads);
    return 0;
}

Đầu vào / Đầu ra

Input: 4, 4, {{1,2,5},{2,3,8},{3,4,7},{4,1,6}}

Output: 26 26 26 26