#include <bits/stdc++.h> using namespace std; typedef long long ll; ll read() { ll n; cin >> n; return n; } #define mp make_pair int main() { int n = read(); int t = read(); vector<ll> z(n); for (int i=0; i<n; ++i) z[i] = read(); map<pair<int, int>, ll> m; for (int i=1; i<n; ++i) { int a = read() - 1; int b = read() - 1; m[mp(a,b)] = m[mp(b,a)] = read(); } int cur = 0; while (t--) { int cmd = read(); if (cmd == 1) { int a = read() - 1; z[a] = read(); } if (cmd == 2) { int a = read() - 1; int b = read() - 1; m[mp(a,b)] = m[mp(b,a)] = read(); } vector<ll> v(n, -1); v[cur] = 0; queue<int> q; q.push(cur); while (!q.empty()) { int x = q.front(); q.pop(); for (auto it = m.lower_bound(mp(x, 0)); it != m.end() && it->first.first == x; ++it) { int y = it->first.second; if (v[y] != -1) continue; int k = it->second; v[y] = v[x] + k; q.push(y); } } int res = cur == 0 ? 1 : 0; for (int i=0; i<n; ++i) if (i != cur) if (z[i] - v[i] > z[res] - v[res]) res = i; cout << (res+1) << " "; cur = res; } 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 | #include <bits/stdc++.h> using namespace std; typedef long long ll; ll read() { ll n; cin >> n; return n; } #define mp make_pair int main() { int n = read(); int t = read(); vector<ll> z(n); for (int i=0; i<n; ++i) z[i] = read(); map<pair<int, int>, ll> m; for (int i=1; i<n; ++i) { int a = read() - 1; int b = read() - 1; m[mp(a,b)] = m[mp(b,a)] = read(); } int cur = 0; while (t--) { int cmd = read(); if (cmd == 1) { int a = read() - 1; z[a] = read(); } if (cmd == 2) { int a = read() - 1; int b = read() - 1; m[mp(a,b)] = m[mp(b,a)] = read(); } vector<ll> v(n, -1); v[cur] = 0; queue<int> q; q.push(cur); while (!q.empty()) { int x = q.front(); q.pop(); for (auto it = m.lower_bound(mp(x, 0)); it != m.end() && it->first.first == x; ++it) { int y = it->first.second; if (v[y] != -1) continue; int k = it->second; v[y] = v[x] + k; q.push(y); } } int res = cur == 0 ? 1 : 0; for (int i=0; i<n; ++i) if (i != cur) if (z[i] - v[i] > z[res] - v[res]) res = i; cout << (res+1) << " "; cur = res; } return 0; } |