Submission #50169663

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
#define int long long
const ll mod = 1000000007, mod2 = 998244353;
const ll INF = 1e18 + 1;
vector<vector<pair<int, int>>> adj;
void solve(){
    int n; cin >> n;
    adj.resize(n);
    for (ll i = 0; i < n - 1; ++i){
        int x, y, z; cin >> x >> y >> z;
        z--;
        adj[i].pb({i + 1, x});
        adj[i].pb({z, y});
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
#define int long long

const ll mod = 1000000007, mod2 = 998244353;
const ll INF = 1e18 + 1;
vector<vector<pair<int, int>>> adj;

void solve(){
    int n; cin >> n;
    adj.resize(n);
    for (ll i = 0; i < n - 1; ++i){
        int x, y, z; cin >> x >> y >> z;
        z--;
        adj[i].pb({i + 1, x});
        adj[i].pb({z, y});
    }
    priority_queue<pair<int, int>> pq;
    vector<int> dis(n, INF);
    dis[0] = 0;
    pq.push({0, 0});
    vector<bool> pro(n, false);
    while(!pq.empty()){
        auto curr = pq.top();
        pq.pop();
        if(pro[curr.sc]) continue;
        pro[curr.sc] = true;
        for (auto [x, y] : adj[curr.sc]) {
            if(dis[x] > dis[curr.sc] + y){
                dis[x] = dis[curr.sc] + y;
                pq.push({-dis[x], x});
            }
        }
    }
    cout << dis[n - 1];
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tt = 1; 
    while(tt--){
        solve();
        cout << endl;
    }
    return 0;
}

Submission Info

Judge Result