#include<cstdio> #include<vector> #include<map> #include<queue> #include<climits> int n,q; long long * profit; std::vector<std::map<int, long long> > graph; bool * visited; long long * cost; void print_graph() { for (int i = 0; i < n; i++) { printf("%d:\n", i + 1); for (std::map<int, long long>::iterator it = graph[i].begin(); it != graph[i].end(); it++) { printf("(%d, %lld) ", it -> first + 1, it -> second); } printf("\n"); } } void input() { scanf("%d %d", &n, &q); profit = new long long[n]; visited = new bool[n]; cost = new long long[n]; for (int i = 0; i < n; i++) { scanf("%lld", profit + i); graph.push_back(std::map<int, long long>()); } int v, w; long long z; for (int i = 0; i < n - 1; i++) { scanf("%d %d %lld", &v, &w, &z); graph[v - 1][w - 1] = z; graph[w - 1][v - 1] = z; } } long long min(long long a, long long b) { return a < b ? a : b; } int progres(int city) { //printf("CITY=%d\n", city); for (int i = 0; i < n; i++) { visited[i] = false; cost[i] = LLONG_MAX; } long long best_profit = LLONG_MIN; int best = city; cost[city] = 0; std::queue<int> Q; Q.push(city); while(!Q.empty()) { int v = Q.front(); //printf("v=%d\n", v); Q.pop(); if (!visited[v]) { visited[v] = true; for (std::map<int, long long>::iterator it = graph[v].begin(); it != graph[v].end(); it++) { int w = it -> first; cost[w] = min(cost[w], cost[v] + it -> second); if (!visited[w]) { Q.push(w); } } } }/* printf("CITY=%d\n", city); print_graph(); for (int i = 0; i < n; i++) { printf("%3lld ", cost[i]); } printf("\n"); for (int i = 0; i < n; i++) { printf("%3lld ", profit[i]); } printf("\n");*/ for (int i = 0; i < n; i++) { if (i != city) { if (best_profit < profit[i] - cost[i]) { best_profit = profit[i] - cost[i]; best = i; } } } return best; } void solve() { int t, a, b; long long c; int city = 0; for (int i = 0; i < q; i++) { scanf("%d", &t); if (t == 1) { scanf("%d %lld", &a, &c); profit[a - 1] = c; } else { scanf("%d %d %lld", &a, &b, &c); graph[a - 1][b - 1] = c; graph[b - 1][a - 1] = c; } city = progres(city); printf("%d ", city + 1); } printf("\n"); } int main(int argc, char ** argv) { input(); solve(); 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 | #include<cstdio> #include<vector> #include<map> #include<queue> #include<climits> int n,q; long long * profit; std::vector<std::map<int, long long> > graph; bool * visited; long long * cost; void print_graph() { for (int i = 0; i < n; i++) { printf("%d:\n", i + 1); for (std::map<int, long long>::iterator it = graph[i].begin(); it != graph[i].end(); it++) { printf("(%d, %lld) ", it -> first + 1, it -> second); } printf("\n"); } } void input() { scanf("%d %d", &n, &q); profit = new long long[n]; visited = new bool[n]; cost = new long long[n]; for (int i = 0; i < n; i++) { scanf("%lld", profit + i); graph.push_back(std::map<int, long long>()); } int v, w; long long z; for (int i = 0; i < n - 1; i++) { scanf("%d %d %lld", &v, &w, &z); graph[v - 1][w - 1] = z; graph[w - 1][v - 1] = z; } } long long min(long long a, long long b) { return a < b ? a : b; } int progres(int city) { //printf("CITY=%d\n", city); for (int i = 0; i < n; i++) { visited[i] = false; cost[i] = LLONG_MAX; } long long best_profit = LLONG_MIN; int best = city; cost[city] = 0; std::queue<int> Q; Q.push(city); while(!Q.empty()) { int v = Q.front(); //printf("v=%d\n", v); Q.pop(); if (!visited[v]) { visited[v] = true; for (std::map<int, long long>::iterator it = graph[v].begin(); it != graph[v].end(); it++) { int w = it -> first; cost[w] = min(cost[w], cost[v] + it -> second); if (!visited[w]) { Q.push(w); } } } }/* printf("CITY=%d\n", city); print_graph(); for (int i = 0; i < n; i++) { printf("%3lld ", cost[i]); } printf("\n"); for (int i = 0; i < n; i++) { printf("%3lld ", profit[i]); } printf("\n");*/ for (int i = 0; i < n; i++) { if (i != city) { if (best_profit < profit[i] - cost[i]) { best_profit = profit[i] - cost[i]; best = i; } } } return best; } void solve() { int t, a, b; long long c; int city = 0; for (int i = 0; i < q; i++) { scanf("%d", &t); if (t == 1) { scanf("%d %lld", &a, &c); profit[a - 1] = c; } else { scanf("%d %d %lld", &a, &b, &c); graph[a - 1][b - 1] = c; graph[b - 1][a - 1] = c; } city = progres(city); printf("%d ", city + 1); } printf("\n"); } int main(int argc, char ** argv) { input(); solve(); return 0; } |