【CSP-J】旅游巴士

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10005;
vector<pair<int, int>> g[N];
int d[N][105];
int state[N][105];
struct Node {
    int u, i, d;
    bool operator<(const Node &rhs) const {
        return d > rhs.d;
    }
};

int main() {
    freopen("bus.in","r",stdin);
    freopen("bus.out","w",stdout);
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    while (m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});  // 修复1: 使用花括号初始化pair
    }

    memset(d, 0x3f, sizeof d);
    priority_queue<Node> q;
    q.push({1, 0, d[1][0] = 0});
    while (q.size()) {
        int u = q.top().u, i = q.top().i;
        q.pop();
        if (state[u][i]) continue;
        state[u][i] = 1;
        for (auto [v, w] : g[u]) {
            int t = d[u][i];
            int j = (i + 1) % k;
            if (t < w) 
                t += (w - t + k - 1) / k * k;
            if (d[v][j] > t + 1) {
                d[v][j] = t + 1;
                q.push({v, j, d[v][j]});  // 修复2: 使用花括号初始化Node
            }
        }
    }
    
    if (d[n][0] == INF) d[n][0] = -1;
    printf("%d\n", d[n][0]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}