Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8.
Możesz pobrać ten plik i spróbować otworzyć go samodzielnie.
#include<cstdio> #include <list> #define N 100000 using namespace std; long long int miasta[N + 10]; struct krawedz { long long int wierzcholek; long long int koszt; }; list<krawedz> sasiedzi[N + 10]; long long int max_zysk; long long int max_wierzcholek; long long int czy_odwiedzony[N + 10]; long long int tryb; int odwiedz_graf(long long int wierzcholek, long long int odwiedzony, long long int myto) { czy_odwiedzony[wierzcholek] = odwiedzony; if (tryb == 1) { max_wierzcholek = wierzcholek; max_zysk = miasta[wierzcholek] - myto; } else if (tryb > 1) { long long int zysk_w = miasta[wierzcholek] - myto; if (zysk_w > max_zysk) { max_zysk = zysk_w; max_wierzcholek = wierzcholek; } else if (zysk_w == max_zysk) { if (wierzcholek < max_wierzcholek) { max_wierzcholek = wierzcholek; } } } for (list<krawedz>::iterator it = sasiedzi[wierzcholek].begin(); it != sasiedzi[wierzcholek].end(); ++it) { if (czy_odwiedzony[(*it).wierzcholek] != odwiedzony) { tryb++; odwiedz_graf((*it).wierzcholek, odwiedzony, myto + (*it).koszt); } } return max_wierzcholek; } int main() { long long int n, q, a, b, miasto; long long int koszt, zysk; krawedz k1, k2; long long int biezacy_wierzcholek = 1; scanf("%lld %lld", &n, &q); for (int i = 1; i <= n; i++) { scanf("%lld", &miasta[i]); } for (int i = 0; i < n - 1; i++) { scanf("%lld %lld %lld", &a, &b, &koszt); k1 = {b, koszt}; sasiedzi[a].push_back(k1); k2 = {a, koszt}; sasiedzi[b].push_back(k2); } for (int i = 0; i < q; i++) { scanf("%lld", &tryb); if (tryb == 1) { scanf("%lld %lld", &miasto, &zysk); miasta[miasto] = zysk; } else if (tryb == 2) { scanf("%lld %lld %lld", &a, &b, &koszt); // zaktualizowa� koszt a -> b for (list<krawedz>::iterator it = sasiedzi[a].begin(); it != sasiedzi[a].end(); ++it) { if ((*it).wierzcholek == b) { (*it).koszt = koszt; break; } } // zaktualizowa� koszt b -> a for (list<krawedz>::iterator it = sasiedzi[b].begin(); it != sasiedzi[b].end(); ++it) { if ((*it).wierzcholek == a) { (*it).koszt = koszt; } } } tryb = 0L; biezacy_wierzcholek = odwiedz_graf(biezacy_wierzcholek, i + 1, 0); printf("%lld ", biezacy_wierzcholek); } 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 | #include<cstdio> #include <list> #define N 100000 using namespace std; long long int miasta[N + 10]; struct krawedz { long long int wierzcholek; long long int koszt; }; list<krawedz> sasiedzi[N + 10]; long long int max_zysk; long long int max_wierzcholek; long long int czy_odwiedzony[N + 10]; long long int tryb; int odwiedz_graf(long long int wierzcholek, long long int odwiedzony, long long int myto) { czy_odwiedzony[wierzcholek] = odwiedzony; if (tryb == 1) { max_wierzcholek = wierzcholek; max_zysk = miasta[wierzcholek] - myto; } else if (tryb > 1) { long long int zysk_w = miasta[wierzcholek] - myto; if (zysk_w > max_zysk) { max_zysk = zysk_w; max_wierzcholek = wierzcholek; } else if (zysk_w == max_zysk) { if (wierzcholek < max_wierzcholek) { max_wierzcholek = wierzcholek; } } } for (list<krawedz>::iterator it = sasiedzi[wierzcholek].begin(); it != sasiedzi[wierzcholek].end(); ++it) { if (czy_odwiedzony[(*it).wierzcholek] != odwiedzony) { tryb++; odwiedz_graf((*it).wierzcholek, odwiedzony, myto + (*it).koszt); } } return max_wierzcholek; } int main() { long long int n, q, a, b, miasto; long long int koszt, zysk; krawedz k1, k2; long long int biezacy_wierzcholek = 1; scanf("%lld %lld", &n, &q); for (int i = 1; i <= n; i++) { scanf("%lld", &miasta[i]); } for (int i = 0; i < n - 1; i++) { scanf("%lld %lld %lld", &a, &b, &koszt); k1 = {b, koszt}; sasiedzi[a].push_back(k1); k2 = {a, koszt}; sasiedzi[b].push_back(k2); } for (int i = 0; i < q; i++) { scanf("%lld", &tryb); if (tryb == 1) { scanf("%lld %lld", &miasto, &zysk); miasta[miasto] = zysk; } else if (tryb == 2) { scanf("%lld %lld %lld", &a, &b, &koszt); // zaktualizowa� koszt a -> b for (list<krawedz>::iterator it = sasiedzi[a].begin(); it != sasiedzi[a].end(); ++it) { if ((*it).wierzcholek == b) { (*it).koszt = koszt; break; } } // zaktualizowa� koszt b -> a for (list<krawedz>::iterator it = sasiedzi[b].begin(); it != sasiedzi[b].end(); ++it) { if ((*it).wierzcholek == a) { (*it).koszt = koszt; } } } tryb = 0L; biezacy_wierzcholek = odwiedz_graf(biezacy_wierzcholek, i + 1, 0); printf("%lld ", biezacy_wierzcholek); } return 0; } |