#include <iostream> #include <vector> #include <unordered_map> #include <queue> #include <set> using namespace std; const long long INF_DIST = 10000000000000000; struct INEdge { int x, y, d; }; struct INQuery { int op; int in1, in3; long long in2; }; int n, m, q; vector<INEdge> IE; vector<INQuery> IQ; // ================== BRUTE FORCE ============================ void brute_force() { vector<unordered_map<int, int>> G(n); vector<int> C(n, 0); for (const auto& ie : IE) { G[ie.x-1][ie.y-1] = ie.d; G[ie.y-1][ie.x-1] = ie.d; } for (const auto& iq : IQ) { if (iq.op == 1) { int a=iq.in1, b=iq.in2, d=iq.in3; G[a-1][b-1] = d; G[b-1][a-1] = d; } else if (iq.op == 2) { int a=iq.in1, b=iq.in2; G[a-1].erase(b-1); G[b-1].erase(a-1); } else if (iq.op == 3) { int v=iq.in1, k=iq.in3; long long z=iq.in2; vector<long long> dist(n, z+1); priority_queue<pair<long long,int>> PQ; // {-dist, vertex} dist[v-1] = 0; PQ.push({0, v-1}); while (!PQ.empty()) { auto [d, vv] = PQ.top(); PQ.pop(); d = -d; if (d != dist[vv]) continue; C[vv] = k; for (auto it=G[vv].begin(); it!=G[vv].end(); it++) { long long dd = d + it->second; if (dd < dist[it->first]) { dist[it->first] = dd; PQ.push({-dd, it->first}); } } } } else { int u=iq.in1; cout << C[u-1] << '\n'; } } } // ====================== STATIC TREE / NO RANGES =================== vector<vector<int>> G; vector<int> T; vector<int> C; void dfs(int v, int p) { for (int nei : G[v]) if (nei != p) { T[nei] = T[v]; dfs(nei, v); } } void static_forest_no_ranges() { G.clear(); G.resize(n); for (const auto& ie : IE) { G[ie.x-1].push_back(ie.y-1); G[ie.y-1].push_back(ie.x-1); } // find trees T.clear(); T.resize(n, -1); for (int i=0; i<n; i++) if (T[i] == -1) { T[i] = C.size(); dfs(i, -1); C.push_back(0); } // queries for (const auto& iq : IQ) { if (iq.op == 3) C[T[iq.in1-1]] = iq.in3; else cout << C[T[iq.in1-1]] << '\n'; } } // ====================== MAIN ======================= int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> q; IE.resize(m); for (auto &ie : IE) cin >> ie.x >> ie.y >> ie.d; IQ.resize(q); for (auto &iq : IQ) { cin >> iq.op >> iq.in1; if (iq.op != 4) { cin >> iq.in2; if (iq.op != 2) cin >> iq.in3; } } bool tree_changes = false; bool range_query = false; for (const auto& iq : IQ) { if (iq.op==1 || iq.op==2) tree_changes = true; if (iq.op==3 && iq.in2 != 1000000000000000) range_query = true; } if (!tree_changes && !range_query) static_forest_no_ranges(); else brute_force(); 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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 | #include <iostream> #include <vector> #include <unordered_map> #include <queue> #include <set> using namespace std; const long long INF_DIST = 10000000000000000; struct INEdge { int x, y, d; }; struct INQuery { int op; int in1, in3; long long in2; }; int n, m, q; vector<INEdge> IE; vector<INQuery> IQ; // ================== BRUTE FORCE ============================ void brute_force() { vector<unordered_map<int, int>> G(n); vector<int> C(n, 0); for (const auto& ie : IE) { G[ie.x-1][ie.y-1] = ie.d; G[ie.y-1][ie.x-1] = ie.d; } for (const auto& iq : IQ) { if (iq.op == 1) { int a=iq.in1, b=iq.in2, d=iq.in3; G[a-1][b-1] = d; G[b-1][a-1] = d; } else if (iq.op == 2) { int a=iq.in1, b=iq.in2; G[a-1].erase(b-1); G[b-1].erase(a-1); } else if (iq.op == 3) { int v=iq.in1, k=iq.in3; long long z=iq.in2; vector<long long> dist(n, z+1); priority_queue<pair<long long,int>> PQ; // {-dist, vertex} dist[v-1] = 0; PQ.push({0, v-1}); while (!PQ.empty()) { auto [d, vv] = PQ.top(); PQ.pop(); d = -d; if (d != dist[vv]) continue; C[vv] = k; for (auto it=G[vv].begin(); it!=G[vv].end(); it++) { long long dd = d + it->second; if (dd < dist[it->first]) { dist[it->first] = dd; PQ.push({-dd, it->first}); } } } } else { int u=iq.in1; cout << C[u-1] << '\n'; } } } // ====================== STATIC TREE / NO RANGES =================== vector<vector<int>> G; vector<int> T; vector<int> C; void dfs(int v, int p) { for (int nei : G[v]) if (nei != p) { T[nei] = T[v]; dfs(nei, v); } } void static_forest_no_ranges() { G.clear(); G.resize(n); for (const auto& ie : IE) { G[ie.x-1].push_back(ie.y-1); G[ie.y-1].push_back(ie.x-1); } // find trees T.clear(); T.resize(n, -1); for (int i=0; i<n; i++) if (T[i] == -1) { T[i] = C.size(); dfs(i, -1); C.push_back(0); } // queries for (const auto& iq : IQ) { if (iq.op == 3) C[T[iq.in1-1]] = iq.in3; else cout << C[T[iq.in1-1]] << '\n'; } } // ====================== MAIN ======================= int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> q; IE.resize(m); for (auto &ie : IE) cin >> ie.x >> ie.y >> ie.d; IQ.resize(q); for (auto &iq : IQ) { cin >> iq.op >> iq.in1; if (iq.op != 4) { cin >> iq.in2; if (iq.op != 2) cin >> iq.in3; } } bool tree_changes = false; bool range_query = false; for (const auto& iq : IQ) { if (iq.op==1 || iq.op==2) tree_changes = true; if (iq.op==3 && iq.in2 != 1000000000000000) range_query = true; } if (!tree_changes && !range_query) static_forest_no_ranges(); else brute_force(); return 0; } |