abc 340 D

从 一点 到所有点的最短距离，dijkstra 算法
这样相比于形似的BFS，BFS只能一层一层考虑，而它可以优先的考虑到很深的位置
优先考虑路程短的点，由于路程短的点的中间点一定也是短于长的不优的点的，所以路程短的一定被优先考虑
dijkstra和BFS相比的一个是层数优先，一个是距离优先
因为是小根堆，优先考虑离得近的，因为每点出度是2，属于稀疏图，时间复杂度为O(n log n) 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> PII;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    ll inf = 1e18;
    vector<ll> dp(n + 1, inf), a(n + 1), b(n + 1), X(n + 1);

    for (int i = 1; i < n; i ++) cin >> a[i] >> b[i] >> X[i];

    priority_queue<PII, vector<PII>, greater<PII>> q;

    vector<ll> dis(n + 1, -1);

    q.push({0, 1});

    while (q.size()) {
        auto [d, x] = q.top();
        q.pop();

        if (dis[x] != -1) continue;

        dis[x] = d;

        q.push({a[x] + d, x + 1});
        q.push({d + b[x], X[x]});
    }

    cout << dis[n] << endl;

    return 0;
}