lessons/参考实现/05-最短路与类最短路/AtCoder-abc340_d.cpp

#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<vector<pair<int, long long>>> g(n);
    for (int i = 0; i + 1 < n; ++i) {
        long long a, b; int x; cin >> a >> b >> x; --x;
        g[i].push_back({i + 1, a}); g[i].push_back({x, b});
    }
    const long long inf = numeric_limits<long long>::max() / 4;
    vector<long long> dist(n, inf); dist[0] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : g[u]) if (dist[v] > d + w) {
            dist[v] = d + w; pq.push({dist[v], v});
        }
    }
    cout << dist[n - 1] << '\n';
}