โปรแกรม C++ ตรวจสอบการเดินทางกลับบ้าน (Round Trip) จากทุกเมือง

มี n เมือง m ถนน חד-ทิศทาง แต่ละถนน (source, dest, time) ต้องการสำหรับแต่ละเมือง หาเวลาน้อยที่สุดของ Round Trip (เริ่มเมืองนั้น เดินทางผ่านถนน ≥1 เส้น กลับมาที่เมืองเดิม) ถ้าไม่มี → -1

ตัวอย่าง: n=4,m=4, roads={{1,2,5},{2,3,8},{3,4,7},{4,1,6}} ผลลัพธ์: 26 26 26 26 (วงจร 1→2→3→4→1 รวม 26)

ขั้นตอนการแก้ปัญหา (Dijkstra จากทุกจุด)

1. สร้างกราฟ graph adjacency list
2. สำหรับแต่ละเมือง i:
   • รัน Dijkstra (priority queue) เริ่มจาก i ระยะทางเริ่มต้น 0
   • เมื่อพบทางกลับมาที่ i อีกครั้ง (dst[i] == 0 แล้วเจอระยะทาง > 0) → นั่นคือ round trip สั้นที่สุด
   • ถ้าไม่เจอ → -1

ตัวอย่างโค้ด 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 (int i = 0; i < m; i++) {
        int x, y, z; tie(x, y, z) = roads[i];
        x--; y--;
        graph[x].emplace_back(y, z);
    }
    for (int i = 0; i < n; i++) {
        priority_queue<pair<int,int>> q;
        vector<int> dst(n, -1);
        q.emplace(0, i);
        while (q.size()) {
            auto [dt, curr] = q.top(); q.pop();
            if (dst[curr] == 0) { dst[curr] = dt; break; }
            if (dst[curr] != -1) continue;
            dst[curr] = dt;
            for (auto [tp, cst] : graph[curr])
                q.emplace(dt + cst, tp);
        }
        if (dst[i] == 0) dst[i] = -1;
        cout << dst[i] << endl;
    }
}

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;
}

อินพุต / เอาต์พุต

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

Output: 26 26 26 26