#include <iostream> #include <vector> #include <queue> #include <map> using namespace std; struct Edge { Edge(long long v1, long long v2) : v1(v1), v2(v2) {} long long v1, v2; }; ostream &operator<<(ostream &s, const Edge &e) { return s << '(' << e.v1 << ", " << e.v2 << ')'; } bool operator<(const Edge &e1, const Edge &e2) { if (e1.v1 != e2.v1) return e1.v1 < e2.v1; return e1.v2 < e2.v2; } struct NodeData { long long profit; vector<int> neighbours; }; NodeData nodes[100003]; map<Edge, long long> edgeCosts; int currentNode = 1; int n, q; long long profits[100003]; long long fakeProfit = 1ll << 62; void bfs() { long long maxProfit = -fakeProfit; long long maxNode = currentNode; for (int i = 1; i <= n; ++i) { profits[i] = fakeProfit; } profits[currentNode] = nodes[currentNode].profit; queue<int> bfsQueue; bfsQueue.push(currentNode); while (not bfsQueue.empty()) { int cn = bfsQueue.front(); // cerr << "current node: " << cn << endl; for (auto n : nodes[cn].neighbours) { if (profits[n] == fakeProfit) { profits[n] = profits[cn] - nodes[cn].profit - edgeCosts[{cn, n}] + nodes[n].profit; // cerr << "new profit for node " << n << " -> " << profits[n] << endl; if (maxProfit < profits[n] or maxProfit == profits[n] and maxNode > n) { maxProfit = profits[n]; maxNode = n; // cerr << "new max node " << n << ", with profit: " << maxProfit << endl; } bfsQueue.push(n); } } bfsQueue.pop(); } // cerr << "profits: "; // for (int i = 1; i < n; ++i) { // cerr << profits[i] << ' '; // } // cerr << endl; currentNode = maxNode; cout << maxNode << ' '; } int main() { cin.sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; for (int i = 1; i <= n; ++i) { cin >> nodes[i].profit; } for (int i = 0; i < n - 1; ++i) { int v1, v2, val; cin >> v1 >> v2; cin >> val; edgeCosts[{v1, v2}] = val; edgeCosts[{v2, v1}] = val; // cerr << Edge{v1, v2} << ", " << val << endl; nodes[v1].neighbours.push_back(v2); nodes[v2].neighbours.push_back(v1); } // cerr << "edge costs: "; // for (auto &edge: edgeCosts) { // cerr << edge.first << " -> " << edge.second << ", "; // } // cerr << endl << "city costs: "; // for (int i = 1; i <= n; ++i) { // cerr << nodes[i].profit << ' '; // } // cerr << endl; for (int i = 0; i < q; ++i) { int var; cin >> var; switch (var) { case 1: { long long city; cin >> city; cin >> nodes[city].profit; break; } case 2: { long long v1, v2, cost; cin >> v1 >> v2 >> cost; edgeCosts[{v1, v2}] = cost; edgeCosts[{v2, v1}] = cost; break; } } // cerr << "edge costs: "; // for (auto &edge: edgeCosts) { // cerr << edge.first << " -> " << edge.second << ", "; // } // cerr << endl << "city costs: "; // for (int i = 1; i <= n; ++i) { // cerr << nodes[i].profit << ' '; // } // cerr << endl; bfs(); } }
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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | #include <iostream> #include <vector> #include <queue> #include <map> using namespace std; struct Edge { Edge(long long v1, long long v2) : v1(v1), v2(v2) {} long long v1, v2; }; ostream &operator<<(ostream &s, const Edge &e) { return s << '(' << e.v1 << ", " << e.v2 << ')'; } bool operator<(const Edge &e1, const Edge &e2) { if (e1.v1 != e2.v1) return e1.v1 < e2.v1; return e1.v2 < e2.v2; } struct NodeData { long long profit; vector<int> neighbours; }; NodeData nodes[100003]; map<Edge, long long> edgeCosts; int currentNode = 1; int n, q; long long profits[100003]; long long fakeProfit = 1ll << 62; void bfs() { long long maxProfit = -fakeProfit; long long maxNode = currentNode; for (int i = 1; i <= n; ++i) { profits[i] = fakeProfit; } profits[currentNode] = nodes[currentNode].profit; queue<int> bfsQueue; bfsQueue.push(currentNode); while (not bfsQueue.empty()) { int cn = bfsQueue.front(); // cerr << "current node: " << cn << endl; for (auto n : nodes[cn].neighbours) { if (profits[n] == fakeProfit) { profits[n] = profits[cn] - nodes[cn].profit - edgeCosts[{cn, n}] + nodes[n].profit; // cerr << "new profit for node " << n << " -> " << profits[n] << endl; if (maxProfit < profits[n] or maxProfit == profits[n] and maxNode > n) { maxProfit = profits[n]; maxNode = n; // cerr << "new max node " << n << ", with profit: " << maxProfit << endl; } bfsQueue.push(n); } } bfsQueue.pop(); } // cerr << "profits: "; // for (int i = 1; i < n; ++i) { // cerr << profits[i] << ' '; // } // cerr << endl; currentNode = maxNode; cout << maxNode << ' '; } int main() { cin.sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; for (int i = 1; i <= n; ++i) { cin >> nodes[i].profit; } for (int i = 0; i < n - 1; ++i) { int v1, v2, val; cin >> v1 >> v2; cin >> val; edgeCosts[{v1, v2}] = val; edgeCosts[{v2, v1}] = val; // cerr << Edge{v1, v2} << ", " << val << endl; nodes[v1].neighbours.push_back(v2); nodes[v2].neighbours.push_back(v1); } // cerr << "edge costs: "; // for (auto &edge: edgeCosts) { // cerr << edge.first << " -> " << edge.second << ", "; // } // cerr << endl << "city costs: "; // for (int i = 1; i <= n; ++i) { // cerr << nodes[i].profit << ' '; // } // cerr << endl; for (int i = 0; i < q; ++i) { int var; cin >> var; switch (var) { case 1: { long long city; cin >> city; cin >> nodes[city].profit; break; } case 2: { long long v1, v2, cost; cin >> v1 >> v2 >> cost; edgeCosts[{v1, v2}] = cost; edgeCosts[{v2, v1}] = cost; break; } } // cerr << "edge costs: "; // for (auto &edge: edgeCosts) { // cerr << edge.first << " -> " << edge.second << ", "; // } // cerr << endl << "city costs: "; // for (int i = 1; i <= n; ++i) { // cerr << nodes[i].profit << ' '; // } // cerr << endl; bfs(); } } |