#include <iostream> #include <map> #include <algorithm> #include <vector> #include <limits> using namespace std; long long zysk[100007]; vector<int> graf[100007]; map<pair<int, int>, long long> kosztDrogi; int aktualneMiasto = 1; bool odwiedzone[100007]; long long maxZysk; void ruszaj(int curr, long long zaplacone) { odwiedzone[curr] = true; for (int i = 0; i < graf[curr].size(); i++) { int odw = graf[curr][i]; if (odwiedzone[odw]) continue; ruszaj(odw, zaplacone + kosztDrogi[{curr, odw}]); } long long calyZysk = zysk[curr] - zaplacone; if (zaplacone != 0 && calyZysk > maxZysk) { maxZysk = calyZysk; aktualneMiasto = curr; } } int main() { ios_base::sync_with_stdio(0); int ileMiast, ileDni; cin >> ileMiast >> ileDni; for (int i = 1; i <= ileMiast; i++) cin >> zysk[i]; int a, b, c, d; for (int i = 0 ; i < ileMiast - 1; i++) { cin >> a >> b >> c; kosztDrogi.insert({{a, b}, c}); kosztDrogi.insert({{b, a}, c}); graf[a].push_back(b); graf[b].push_back(a); } for (int i = 0; i < ileDni; i++) { cin >> a >> b >> c; if (a == 1) zysk[b] = c; else { cin >> d; kosztDrogi[{b, c}] = d; kosztDrogi[{c, b}] = d; } for (int j = 0; j <= ileMiast; j++) odwiedzone[j] = false; maxZysk = numeric_limits<long long>::min(); ruszaj(aktualneMiasto, 0); cout << aktualneMiasto << " "; } cout << "\n"; }
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 | #include <iostream> #include <map> #include <algorithm> #include <vector> #include <limits> using namespace std; long long zysk[100007]; vector<int> graf[100007]; map<pair<int, int>, long long> kosztDrogi; int aktualneMiasto = 1; bool odwiedzone[100007]; long long maxZysk; void ruszaj(int curr, long long zaplacone) { odwiedzone[curr] = true; for (int i = 0; i < graf[curr].size(); i++) { int odw = graf[curr][i]; if (odwiedzone[odw]) continue; ruszaj(odw, zaplacone + kosztDrogi[{curr, odw}]); } long long calyZysk = zysk[curr] - zaplacone; if (zaplacone != 0 && calyZysk > maxZysk) { maxZysk = calyZysk; aktualneMiasto = curr; } } int main() { ios_base::sync_with_stdio(0); int ileMiast, ileDni; cin >> ileMiast >> ileDni; for (int i = 1; i <= ileMiast; i++) cin >> zysk[i]; int a, b, c, d; for (int i = 0 ; i < ileMiast - 1; i++) { cin >> a >> b >> c; kosztDrogi.insert({{a, b}, c}); kosztDrogi.insert({{b, a}, c}); graf[a].push_back(b); graf[b].push_back(a); } for (int i = 0; i < ileDni; i++) { cin >> a >> b >> c; if (a == 1) zysk[b] = c; else { cin >> d; kosztDrogi[{b, c}] = d; kosztDrogi[{c, b}] = d; } for (int j = 0; j <= ileMiast; j++) odwiedzone[j] = false; maxZysk = numeric_limits<long long>::min(); ruszaj(aktualneMiasto, 0); cout << aktualneMiasto << " "; } cout << "\n"; } |