Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Chương trình C++ tìm thời gian tối thiểu đi tàu giữa các ga

Mô tả bài toán

Có n ga, m đường ray hai chiều. Từ ga j, tàu khởi hành đi các ga liền kề tại các bội số của k_j, mỗi chuyến mất t_j thời gian. Tìm thời gian sớm nhất đến ga dst từ src (bỏ qua thời gian chuyển tàu).

Ví dụ

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

Thuật toán (Dijkstra biến đổi)

  1. Xây đồ thị: mỗi cạnh lưu (đích, t, k).
  2. Mảng dp lưu thời gian đến sớm nhất (khởi tạo -∞).
  3. Hàng đợi ưu tiên max-heap theo -time (vì muốn lấy thời gian nhỏ nhất).
  4. Khi ở ga a lúc w, tàu đến ga b lúc weight = ceil((w+1)/k)*k - t (công thức trong code).
  5. Cập nhật dp[b] nếu weight > dp[b] (lưu ý dấu âm trong heap).

Đoạn mã 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 dp[b]) {
                dp[b]=weight;
                pq.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;
}

Đầu vào / Đầu ra

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

Output: 8