#include <iostream> #include <climits> #include <vector> #include <utility> using namespace std; struct Node { long long value; int node_no; vector<pair<Node*, int> > children; Node(int node, int val){ this->node_no = node; this->value = val; } void changeConnectionValue(int destination, int new_val){ for(int x=0; x<this->children.size(); x++){ if(this->children[x].first->node_no == destination){ this->children[x].second = new_val; } } } }; Node *cities[100000]; bool* visited; pair<Node*, long long> findBest(Node* currentNode, long long currentScore){ long long maxScore = currentScore + currentNode->value; Node* maxCity = currentNode; if(currentScore == 0){ maxScore = INT_MIN; } for(int i=0; i<currentNode->children.size(); i++){ Node* thisCity = currentNode->children[i].first; if(!visited[thisCity->node_no]){ long long connectionPrice = currentNode->children[i].second; visited[thisCity->node_no] = true; pair<Node*, long long> score = findBest(cities[thisCity->node_no], currentScore - connectionPrice); visited[thisCity->node_no] = false; if(score.second > maxScore || (score.second == maxScore && score.first->node_no < maxCity->node_no)){ maxScore = score.second; maxCity = score.first; } } } return make_pair(maxCity, maxScore); } int main(){ int city_num, day_num; cin >> city_num >> day_num; visited = new bool[city_num]; for(int i=0; i<city_num; i++){ int val; cin >> val; cities[i] = new Node(i, val); } for(int i=0; i<city_num-1; i++){ int source, destination, price; cin >> source >> destination >> price; source--; destination--; cities[source]->children.push_back(make_pair(cities[destination], price)); cities[destination]->children.push_back(make_pair(cities[source], price)); } int prevCity = 0; for(int day=0; day<day_num; day++){ int type; cin >> type; if(type == 1){ int city, new_val; cin >> city >> new_val; city--; cities[city]->value = new_val; } else { int source, destination, new_val; cin >> source >> destination >> new_val; source--; destination--; cities[source]->changeConnectionValue(destination, new_val); cities[destination]->changeConnectionValue(source, new_val); } for(int i=0; i<city_num; i++){ visited[i] = false; } visited[prevCity] = true; long long bestCity = findBest(cities[prevCity], 0).first->node_no; cout << bestCity+1 << " "; prevCity = bestCity; } 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 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 | #include <iostream> #include <climits> #include <vector> #include <utility> using namespace std; struct Node { long long value; int node_no; vector<pair<Node*, int> > children; Node(int node, int val){ this->node_no = node; this->value = val; } void changeConnectionValue(int destination, int new_val){ for(int x=0; x<this->children.size(); x++){ if(this->children[x].first->node_no == destination){ this->children[x].second = new_val; } } } }; Node *cities[100000]; bool* visited; pair<Node*, long long> findBest(Node* currentNode, long long currentScore){ long long maxScore = currentScore + currentNode->value; Node* maxCity = currentNode; if(currentScore == 0){ maxScore = INT_MIN; } for(int i=0; i<currentNode->children.size(); i++){ Node* thisCity = currentNode->children[i].first; if(!visited[thisCity->node_no]){ long long connectionPrice = currentNode->children[i].second; visited[thisCity->node_no] = true; pair<Node*, long long> score = findBest(cities[thisCity->node_no], currentScore - connectionPrice); visited[thisCity->node_no] = false; if(score.second > maxScore || (score.second == maxScore && score.first->node_no < maxCity->node_no)){ maxScore = score.second; maxCity = score.first; } } } return make_pair(maxCity, maxScore); } int main(){ int city_num, day_num; cin >> city_num >> day_num; visited = new bool[city_num]; for(int i=0; i<city_num; i++){ int val; cin >> val; cities[i] = new Node(i, val); } for(int i=0; i<city_num-1; i++){ int source, destination, price; cin >> source >> destination >> price; source--; destination--; cities[source]->children.push_back(make_pair(cities[destination], price)); cities[destination]->children.push_back(make_pair(cities[source], price)); } int prevCity = 0; for(int day=0; day<day_num; day++){ int type; cin >> type; if(type == 1){ int city, new_val; cin >> city >> new_val; city--; cities[city]->value = new_val; } else { int source, destination, new_val; cin >> source >> destination >> new_val; source--; destination--; cities[source]->changeConnectionValue(destination, new_val); cities[destination]->changeConnectionValue(source, new_val); } for(int i=0; i<city_num; i++){ visited[i] = false; } visited[prevCity] = true; long long bestCity = findBest(cities[prevCity], 0).first->node_no; cout << bestCity+1 << " "; prevCity = bestCity; } cout << "\n"; } |