问题描述
高桥正在玩一个游戏。
这个游戏由编号为\(1, 2, \ldots, N\)的\(N\)个阶段组成。最初，只有阶段\(1\)是可以玩的。
对于每个可以玩的阶段\(i\)（其中\(1 \leq i \leq N-1\)），在阶段\(i\)你可以执行以下两个动作之一：
- 花费\(A_i\)秒来通过阶段\(i\)。这允许你进入并玩阶段\(i+1\)。
- 花费\(B_i\)秒来通过阶段\(i\)。这允许你进入并玩阶段\(X_i\)，其中\(X_i\)是另一个阶段，满足\(1 \leq X_i \leq N\)。
忽略除了通过阶段所需时间之外的所有时间，最少需要多少秒才能玩到阶段\(N\)？
约束条件
- \(2 \leq N \leq 2 \times 10^5\)
- \(1 \leq A_i, B_i \leq 10^9\)
- \(1 \leq X_i \leq N\)
- 所有输入值都是整数。
#include<bits/stdc++.h>
#define pt printf(">>>")
#define mid (((l)+(r))/2)
using namespace std;
typedef long long ll;
const ll N=1e6+10,inf=1e18+10,mod=1e9+7;
ll n;
vector<pair<ll,ll> > G[N];
ll d[N],vis[N];
void dijkstra(){
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > que;
fill(d,d+1+n,inf);
que.push(make_pair(d[1]=0,1));
while(que.size()){
ll u=que.top().second;que.pop();
if(vis[u])continue;
vis[u]=true;
for(auto e:G[u]){
ll v=e.first,w=e.second;
if(d[v]>d[u]+w)d[v]=d[u]+w,que.push(make_pair(d[v],v));
}
}
}
int main(){
cin >> n;
for(ll i=1;i<=n-1;i++){
ll a,b,x;
cin >> a >> b >> x;
G[i].push_back(make_pair(i+1,a));
G[i].push_back(make_pair(x,b));
}
dijkstra();
cout << d[n];
return 0;
}