#include<cstdio> #include<vector> #include<map> #include<utility> #include<algorithm> #include<climits> using namespace std; pair<int, long long> find_best_dest(int prev_city, int start_city, vector<long long>& cities, vector<map<int, long long> >& edges) { //printf("Starting with: %d, %d\n", prev_city, start_city); long long best_income = LLONG_MIN; int best_dest = -1; for (map<int, long long>::iterator it = edges[start_city].begin(); it != edges[start_city].end(); ++it) { int city = it->first; //printf("Checking next city: %d\n", city); if (city != prev_city) { long long cost = it->second; long long city_income = cities[city] - cost; //printf("City income: %lld\n", city_income); if (city_income > best_income || (city_income == best_income && city < best_dest)) { best_dest = city; best_income = city_income; } pair<int, long long> city_result = find_best_dest(start_city, city, cities, edges); //printf("City %d result: <%d, %lld>\n", city, city_result.first, city_result.second); long long candidate_res = city_result.second - cost; if (city_result.first != -1 && (candidate_res > best_income || (candidate_res == best_income && city_result.first < best_dest))) { best_dest = city_result.first; best_income = candidate_res; } } } //printf("Result for start city %d: <%d, %lld>\n", start_city, best_dest, best_income); return make_pair(best_dest, best_income); } int main() { int n, q; scanf("%d %d\n", &n, &q); vector<long long> cities(n); for (int i = 0; i < n; i++) { scanf("%lld", &cities[i]); } vector<map<int, long long> > edges; for (int i = 0; i < n; i++) { map<int, long long> tmp_map; edges.push_back(tmp_map); } for (int i = 0; i < n - 1; i++) { int city_a, city_b; long long cost; scanf("%d %d %lld\n", &city_a, &city_b, &cost); edges[city_a - 1][city_b - 1] = cost; edges[city_b - 1][city_a - 1] = cost; } int curr_city = 0; for (int i = 0; i < q; i++) { int type; scanf("%d", &type); if (type == 1) { int city; long long income; scanf("%d %lld\n", &city, &income); cities[city - 1] = income; } else { int city_a, city_b; long long cost; scanf("%d %d %lld\n", &city_a, &city_b, &cost); edges[city_a - 1][city_b - 1] = cost; edges[city_b - 1][city_a - 1] = cost; } pair<int, long long> res = find_best_dest(curr_city, curr_city, cities, edges); curr_city = res.first; printf("%d", curr_city + 1); printf(i < q - 1 ? " " : "\n"); } 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 | #include<cstdio> #include<vector> #include<map> #include<utility> #include<algorithm> #include<climits> using namespace std; pair<int, long long> find_best_dest(int prev_city, int start_city, vector<long long>& cities, vector<map<int, long long> >& edges) { //printf("Starting with: %d, %d\n", prev_city, start_city); long long best_income = LLONG_MIN; int best_dest = -1; for (map<int, long long>::iterator it = edges[start_city].begin(); it != edges[start_city].end(); ++it) { int city = it->first; //printf("Checking next city: %d\n", city); if (city != prev_city) { long long cost = it->second; long long city_income = cities[city] - cost; //printf("City income: %lld\n", city_income); if (city_income > best_income || (city_income == best_income && city < best_dest)) { best_dest = city; best_income = city_income; } pair<int, long long> city_result = find_best_dest(start_city, city, cities, edges); //printf("City %d result: <%d, %lld>\n", city, city_result.first, city_result.second); long long candidate_res = city_result.second - cost; if (city_result.first != -1 && (candidate_res > best_income || (candidate_res == best_income && city_result.first < best_dest))) { best_dest = city_result.first; best_income = candidate_res; } } } //printf("Result for start city %d: <%d, %lld>\n", start_city, best_dest, best_income); return make_pair(best_dest, best_income); } int main() { int n, q; scanf("%d %d\n", &n, &q); vector<long long> cities(n); for (int i = 0; i < n; i++) { scanf("%lld", &cities[i]); } vector<map<int, long long> > edges; for (int i = 0; i < n; i++) { map<int, long long> tmp_map; edges.push_back(tmp_map); } for (int i = 0; i < n - 1; i++) { int city_a, city_b; long long cost; scanf("%d %d %lld\n", &city_a, &city_b, &cost); edges[city_a - 1][city_b - 1] = cost; edges[city_b - 1][city_a - 1] = cost; } int curr_city = 0; for (int i = 0; i < q; i++) { int type; scanf("%d", &type); if (type == 1) { int city; long long income; scanf("%d %lld\n", &city, &income); cities[city - 1] = income; } else { int city_a, city_b; long long cost; scanf("%d %d %lld\n", &city_a, &city_b, &cost); edges[city_a - 1][city_b - 1] = cost; edges[city_b - 1][city_a - 1] = cost; } pair<int, long long> res = find_best_dest(curr_city, curr_city, cities, edges); curr_city = res.first; printf("%d", curr_city + 1); printf(i < q - 1 ? " " : "\n"); } return 0; } |