#include <stdio.h> #include <unordered_map> int n,m; long long int P[100010]; long long int D[100010]; std::unordered_map<int, long long int> V[100010]; int a,b; long long int c; int k,g; void Clear() { for (int i=1;i<=n;i++) { D[i] = -1; } } void Recompute(int x) { for (const auto& kv : V[x]) { if (D[kv.first] != -1) { continue; } D[kv.first] = D[x] + kv.second; Recompute(kv.first); } } int FindMax(int k) { long long int mm = -100000LL * 1000000LL * 1000000LL - 15LL; int qq = 1; for (int i=1;i<=n;i++) { if (i==k) continue; if (P[i] - D[i] > mm) { qq = i; mm = P[i] - D[i]; } } return qq; } main() { scanf("%d", &n); scanf("%d", &m); for (int i=1;i<=n;i++) { scanf("%lld", &P[i]); } for (int i=1;i<n;i++) { scanf("%d", &a); scanf("%d", &b); scanf("%lld", &c); V[a][b] = c; V[b][a] = c; } k=1; for (int i=0;i<m;i++) { scanf("%d", &g); if (g == 1) { scanf("%d", &a); scanf("%lld", &P[a]); } if (g == 2) { scanf("%d", &a); scanf("%d", &b); scanf("%lld", &c); V[a][b] = c; V[b][a] = c; } Clear(); D[k] = 0; Recompute(k); k = FindMax(k); printf("%d ", k); } }
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 | #include <stdio.h> #include <unordered_map> int n,m; long long int P[100010]; long long int D[100010]; std::unordered_map<int, long long int> V[100010]; int a,b; long long int c; int k,g; void Clear() { for (int i=1;i<=n;i++) { D[i] = -1; } } void Recompute(int x) { for (const auto& kv : V[x]) { if (D[kv.first] != -1) { continue; } D[kv.first] = D[x] + kv.second; Recompute(kv.first); } } int FindMax(int k) { long long int mm = -100000LL * 1000000LL * 1000000LL - 15LL; int qq = 1; for (int i=1;i<=n;i++) { if (i==k) continue; if (P[i] - D[i] > mm) { qq = i; mm = P[i] - D[i]; } } return qq; } main() { scanf("%d", &n); scanf("%d", &m); for (int i=1;i<=n;i++) { scanf("%lld", &P[i]); } for (int i=1;i<n;i++) { scanf("%d", &a); scanf("%d", &b); scanf("%lld", &c); V[a][b] = c; V[b][a] = c; } k=1; for (int i=0;i<m;i++) { scanf("%d", &g); if (g == 1) { scanf("%d", &a); scanf("%lld", &P[a]); } if (g == 2) { scanf("%d", &a); scanf("%d", &b); scanf("%lld", &c); V[a][b] = c; V[b][a] = c; } Clear(); D[k] = 0; Recompute(k); k = FindMax(k); printf("%d ", k); } } |