#include <iostream> #include <vector> #include <unordered_map> #include <deque> #include <algorithm> using i64 = int64_t; struct Graph { Graph(int size) : conn(size) , cost(size) { } std::vector<std::unordered_map<int, i64>> conn; std::vector<i64> cost; }; int bfs(Graph const &g, int s) { int num_verts = g.cost.size(); std::deque<int> q; q.push_back(s); std::vector<i64> cs(num_verts, 0); std::vector<bool> vs(num_verts, false); vs[s] = true; while (!q.empty()) { int t = q.front(); q.pop_front(); for (auto &&v: g.conn[t]) { if (!vs[v.first]) { vs[v.first] = true; q.push_back(v.first); cs[v.first] = cs[t] + v.second; } } } int best_node = s; i64 best_cost = std::numeric_limits<i64>::min(); for (int i = 0; i < num_verts; ++i) { if (i == s) continue; if (g.cost[i] - cs[i] > best_cost) { best_cost = g.cost[i] - cs[i]; best_node = i; } else if (g.cost[i] - cs[i] == best_cost) { best_node = std::min(best_node, i); } } return best_node; } int main() { int n, q; std::cin >> n >> q; Graph g(n); for (int i = 0; i < n; ++i) { std::cin >> g.cost[i]; } for (int i = 1; i < n; ++i) { int a, b; i64 c; std::cin >> a >> b >> c; g.conn[a - 1][b - 1] = c; g.conn[b - 1][a - 1] = c; } int s = 0; std::vector<int> res(n); for (int i = 0; i < q; ++i) { int c; std::cin >> c; if (c == 1) { int v; i64 d; std::cin >> v >> d; g.cost[v - 1] = d; } else { int a, b; i64 d; std::cin >> a >> b >> d; g.conn[a - 1][b - 1] = d; g.conn[b - 1][a - 1] = d; } s = bfs(g, s); res[i] = s; } for (auto &&r: res) { std::cout << r + 1 << ' '; } 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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include <iostream> #include <vector> #include <unordered_map> #include <deque> #include <algorithm> using i64 = int64_t; struct Graph { Graph(int size) : conn(size) , cost(size) { } std::vector<std::unordered_map<int, i64>> conn; std::vector<i64> cost; }; int bfs(Graph const &g, int s) { int num_verts = g.cost.size(); std::deque<int> q; q.push_back(s); std::vector<i64> cs(num_verts, 0); std::vector<bool> vs(num_verts, false); vs[s] = true; while (!q.empty()) { int t = q.front(); q.pop_front(); for (auto &&v: g.conn[t]) { if (!vs[v.first]) { vs[v.first] = true; q.push_back(v.first); cs[v.first] = cs[t] + v.second; } } } int best_node = s; i64 best_cost = std::numeric_limits<i64>::min(); for (int i = 0; i < num_verts; ++i) { if (i == s) continue; if (g.cost[i] - cs[i] > best_cost) { best_cost = g.cost[i] - cs[i]; best_node = i; } else if (g.cost[i] - cs[i] == best_cost) { best_node = std::min(best_node, i); } } return best_node; } int main() { int n, q; std::cin >> n >> q; Graph g(n); for (int i = 0; i < n; ++i) { std::cin >> g.cost[i]; } for (int i = 1; i < n; ++i) { int a, b; i64 c; std::cin >> a >> b >> c; g.conn[a - 1][b - 1] = c; g.conn[b - 1][a - 1] = c; } int s = 0; std::vector<int> res(n); for (int i = 0; i < q; ++i) { int c; std::cin >> c; if (c == 1) { int v; i64 d; std::cin >> v >> d; g.cost[v - 1] = d; } else { int a, b; i64 d; std::cin >> a >> b >> d; g.conn[a - 1][b - 1] = d; g.conn[b - 1][a - 1] = d; } s = bfs(g, s); res[i] = s; } for (auto &&r: res) { std::cout << r + 1 << ' '; } return 0; } |