#include<bits/stdc++.h> using namespace std; //#define mod 10000000009; #define int long long vector<pair<int, int> > drogi[100010]; int war[100010]; pair<int, int> odl[100010]; int n; priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int> >, greater<pair<pair<int, int>, int> > > kol; void algo( int pocz ) { for( int i=1; i<=n; i++ ) { if( i == pocz ) { odl[i] = {numeric_limits<int>::max(), 0}; continue; } odl[i] = {-war[i], i}; kol.push( {odl[i], i} ); } pair<int, int> pom; int gdzie; while( !kol.empty() ) { gdzie = kol.top().second; pom = kol.top().first; kol.pop(); if( odl[gdzie] < pom ) continue; for( pair<int, int> & i : drogi[gdzie] ) { pom.first += i.second; if( odl[i.first] > pom ) { odl[i.first] = pom; kol.push( {pom, i.first} ); } pom.first -= i.second; } } } int32_t main() { ios_base::sync_with_stdio( 0 ); cin.tie( 0 ); int q; cin >> n >> q; for( int i=1; i<=n; i++ ) { cin >> war[i]; } for( int a, b, c, i=1; i<n; i++ ) { cin >> a >> b >> c; drogi[a].push_back( {b, c} ); drogi[b].push_back( {a, c} ); } int a, b, c; int gdzie=1; while( q-- ) { cin >> a; if( a==1 ) { cin >> a >> b; war[a] = b; } else { cin >> a >> b >> c; for( pair<int, int> & i : drogi[a] ) { if( i.first == b ) i.second = c; } for( pair<int, int> & i : drogi[b] ) { if( i.first == a ) i.second = c; } } algo( gdzie ); gdzie = odl[gdzie].second; cout << gdzie << " "; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include<bits/stdc++.h> using namespace std; //#define mod 10000000009; #define int long long vector<pair<int, int> > drogi[100010]; int war[100010]; pair<int, int> odl[100010]; int n; priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int> >, greater<pair<pair<int, int>, int> > > kol; void algo( int pocz ) { for( int i=1; i<=n; i++ ) { if( i == pocz ) { odl[i] = {numeric_limits<int>::max(), 0}; continue; } odl[i] = {-war[i], i}; kol.push( {odl[i], i} ); } pair<int, int> pom; int gdzie; while( !kol.empty() ) { gdzie = kol.top().second; pom = kol.top().first; kol.pop(); if( odl[gdzie] < pom ) continue; for( pair<int, int> & i : drogi[gdzie] ) { pom.first += i.second; if( odl[i.first] > pom ) { odl[i.first] = pom; kol.push( {pom, i.first} ); } pom.first -= i.second; } } } int32_t main() { ios_base::sync_with_stdio( 0 ); cin.tie( 0 ); int q; cin >> n >> q; for( int i=1; i<=n; i++ ) { cin >> war[i]; } for( int a, b, c, i=1; i<n; i++ ) { cin >> a >> b >> c; drogi[a].push_back( {b, c} ); drogi[b].push_back( {a, c} ); } int a, b, c; int gdzie=1; while( q-- ) { cin >> a; if( a==1 ) { cin >> a >> b; war[a] = b; } else { cin >> a >> b >> c; for( pair<int, int> & i : drogi[a] ) { if( i.first == b ) i.second = c; } for( pair<int, int> & i : drogi[b] ) { if( i.first == a ) i.second = c; } } algo( gdzie ); gdzie = odl[gdzie].second; cout << gdzie << " "; } return 0; } |