โปรแกรม C++ หาเวลาน้อยที่สุดเดินทางโดยรถไฟระหว่างสถานี

มี n สถานี เชื่อมด้วย m ราง (สองทาง) ต้องเดินทางจาก src ไป dst รางที่ i เชื่อม {station1, station2} จากสถานี j รถไฟออกทุก k_j หน่วยเวลา (คูณของ k_j) และใช้เวลา t_j ถึงสถานีปลายทาง ข้อมูลใน departure = {{t_j, k_j}} สามารถเปลี่ยนรถไฟได้ทันที (เวลาเปลี่ยน = 0) หาเวลาน้อยที่สุดจาก src ถึง dst

ตัวอย่าง: n=4, m=3, src=1, dst=4, roads={{1,2},{2,4},{3,4}}, departure={{2,1},{3,5},{7,6}} ผลลัพธ์: 8 (สถานี 1→2 เวลา 0 ถึงเวลา 2, สถานี 2→4 รอจนเวลา 5 ถึงเวลา 8)

ขั้นตอนการแก้ปัญหา (Dijkstra แบบปรับเปลี่ยน)

1. สร้างกราฟ graph โดยแต่ละขอบเก็บ (ปลายทาง, t, k)
2. อาร์เรย์ dp เก็บเวลาล่าสุดที่ถึงแต่ละสถานี (เริ่มต้น -9999)
3. Priority Queue (max-heap โดยเก็บค่าลบ) เริ่มจาก src เวลา 0
4. ขณะคิวไม่ว่าง:
   • ดึง (w, a) ถ้า a == dst คืน -w
   • ถ้า w < dp[a] ข้าม
   • สำหรับขอบ (b, t, k) จาก a คำนวณ weight = (w - k + 1) / k * k - t (เวลาออกเดินทางล่าสุดก่อนถึง a)
   • ถ้า weight > dp[b] อัปเดตและ push เข้าคิว

ตัวอย่างโค้ด C++

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

int solve(int n, int m, int src, int dst,
          vector<pair<int, int>> roads,
          vector<pair<int, int>> departure) {
    src--; dst--;
    vector<tuple<int, int, int>> graph[n];
    for (int i = 0; i < m; i++) {
        int a = roads[i].first - 1;
        int b = roads[i].second - 1;
        int t = departure[i].first;
        int k = departure[i].second;
        graph[a].emplace_back(b, t, k);
        graph[b].emplace_back(a, t, k);
    }
    vector<int> dp(n, -9999);
    priority_queue<pair<int, int>> priq;
    dp[src] = 0;
    priq.push({-dp[src], src});
    while (!priq.empty()) {
        auto [w, a] = priq.top(); priq.pop();
        if (a == dst) return -w;
        if (w < dp[a]) continue;
        for (auto &v : graph[a]) {
            int b, t, k;
            tie(b, t, k) = v;
            int weight = (w - k + 1) / k * k - t;
            if (weight > dp[b]) {
                dp[b] = weight;
                priq.push({weight, b});
            }
        }
    }
    return -1;
}

int main() {
    int n = 4, m = 3, src = 1, dst = 4;
    vector<pair<int, int>> roads = {{1, 2}, {2, 4}, {3, 4}};
    vector<pair<int, int>> departure = {{2, 1}, {3, 5}, {7, 6}};
    cout << solve(n, m, src, dst, roads, departure);
    return 0;
}

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

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

Output: 8