#include <cstdio> #include <vector> #include <unordered_map> #include <queue> using namespace std; const int MAXN = 100000; const int MAXQ = 100000; const int PROFIT_CHANGE = 1; const int COST_CHANGE = 2; typedef long long int ll; const ll INF = 1000000000100000000; typedef pair <int, ll> P; int n, q; int a, b; int current_city = 1; ll c; ll city_profit[MAXN + 5]; ll city_cost[MAXN + 5]; bool vis[MAXN + 5]; unordered_map<int,ll> M[MAXN + 5]; unordered_map<int,ll>::iterator it; int get_city_num(); int main() { scanf("%d %d", &n, &q); for(int i = 1; i <= n; ++i) { scanf("%lld", &city_profit[i]); } for(int i = 1; i < n; ++i) { scanf("%d %d %lld", &a, &b, &c); M[a][b] = c; M[b][a] = c; } for(int i = 0; i < q; ++i) { int c_type; scanf("%d", &c_type); if(c_type == PROFIT_CHANGE) { int city; ll new_profit; scanf("%d %lld", &city, &new_profit); city_profit[city] = new_profit; } else if(c_type == COST_CHANGE) { scanf("%d %d %lld", &a, &b, &c); M[a][b] = c; M[b][a] = c; } printf("%d ", get_city_num()); } printf("\n"); return 0; } int get_city_num() { for(int i = 1; i <= n; ++i) { city_cost[i] = 0LL; vis[i] = false; } queue <int> Q; Q.push(current_city); P best; best.first = -1; best.second = -INF; vis[current_city] = true; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(it = M[u].begin(); it != M[u].end(); ++it) { int v = (*it).first; ll road_cost = (*it).second; if(!vis[v]) { city_cost[v] = city_cost[u] + road_cost; ll city_result = city_profit[v] - city_cost[v]; if(city_result > best.second or (city_result == best.second and v < best.first)) { best.first = v; best.second = city_result; } vis[v] = true; Q.push(v); } } } return current_city = best.first; }
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 | #include <cstdio> #include <vector> #include <unordered_map> #include <queue> using namespace std; const int MAXN = 100000; const int MAXQ = 100000; const int PROFIT_CHANGE = 1; const int COST_CHANGE = 2; typedef long long int ll; const ll INF = 1000000000100000000; typedef pair <int, ll> P; int n, q; int a, b; int current_city = 1; ll c; ll city_profit[MAXN + 5]; ll city_cost[MAXN + 5]; bool vis[MAXN + 5]; unordered_map<int,ll> M[MAXN + 5]; unordered_map<int,ll>::iterator it; int get_city_num(); int main() { scanf("%d %d", &n, &q); for(int i = 1; i <= n; ++i) { scanf("%lld", &city_profit[i]); } for(int i = 1; i < n; ++i) { scanf("%d %d %lld", &a, &b, &c); M[a][b] = c; M[b][a] = c; } for(int i = 0; i < q; ++i) { int c_type; scanf("%d", &c_type); if(c_type == PROFIT_CHANGE) { int city; ll new_profit; scanf("%d %lld", &city, &new_profit); city_profit[city] = new_profit; } else if(c_type == COST_CHANGE) { scanf("%d %d %lld", &a, &b, &c); M[a][b] = c; M[b][a] = c; } printf("%d ", get_city_num()); } printf("\n"); return 0; } int get_city_num() { for(int i = 1; i <= n; ++i) { city_cost[i] = 0LL; vis[i] = false; } queue <int> Q; Q.push(current_city); P best; best.first = -1; best.second = -INF; vis[current_city] = true; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(it = M[u].begin(); it != M[u].end(); ++it) { int v = (*it).first; ll road_cost = (*it).second; if(!vis[v]) { city_cost[v] = city_cost[u] + road_cost; ll city_result = city_profit[v] - city_cost[v]; if(city_result > best.second or (city_result == best.second and v < best.first)) { best.first = v; best.second = city_result; } vis[v] = true; Q.push(v); } } } return current_city = best.first; } |