#include <iostream> #include <unordered_map> #include <string> #include <sstream> using namespace std; struct City { int thisIndex; long long profit; unordered_map<int, long long> costs; int getBestCity(); pair<int, long long> getBestCity(long long currentProfit, int from); }; City cities[100010]; int City::getBestCity() { pair<int, long long> result; for (auto& cityWithCost : costs) { auto bestFromNeighbour = cities[cityWithCost.first].getBestCity(0 - cityWithCost.second, thisIndex); if (bestFromNeighbour.second > result.second) result = bestFromNeighbour; } return result.first; } pair<int, long long> City::getBestCity(long long currentProfit, int from) { pair<int, long long> result(thisIndex, currentProfit + profit); for (auto& cityWithCost : costs) { if (cityWithCost.first != from) { auto bestFromNeighbour = cities[cityWithCost.first].getBestCity(currentProfit - cityWithCost.second, thisIndex); if (bestFromNeighbour.second > result.second || (bestFromNeighbour.second == result.second && bestFromNeighbour.first < result.first)) result = bestFromNeighbour; } } return result; } int main() { ios_base::sync_with_stdio(false); for (int i = 0; i < 100010; ++i) { cities[i].thisIndex = i; } int cityCount, dayCount; cin >> cityCount >> dayCount; for (int i = 1; i <= cityCount; ++i) { int tmpProfit; cin >> tmpProfit; cities[i].profit = tmpProfit; } for (int path = 0; path < cityCount-1; ++path) { int tmpA, tmpB; long long tmpC; cin >> tmpA >> tmpB >> tmpC; cities[tmpA].costs[tmpB] = tmpC; cities[tmpB].costs[tmpA] = tmpC; } int currentCityIndex = 1; for (int day = 0; day < dayCount; ++day) { int changeType; cin >> changeType; if (changeType == 1) { int cityIndex; long long newProfit; cin >> cityIndex >> newProfit; cities[cityIndex].profit = newProfit; } else { int cityA, cityB; long long newCost; cin >> cityA >> cityB >> newCost; cities[cityA].costs[cityB] = newCost; cities[cityB].costs[cityA] = newCost; } currentCityIndex = cities[currentCityIndex].getBestCity(); cout << currentCityIndex << ' '; } }
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 | #include <iostream> #include <unordered_map> #include <string> #include <sstream> using namespace std; struct City { int thisIndex; long long profit; unordered_map<int, long long> costs; int getBestCity(); pair<int, long long> getBestCity(long long currentProfit, int from); }; City cities[100010]; int City::getBestCity() { pair<int, long long> result; for (auto& cityWithCost : costs) { auto bestFromNeighbour = cities[cityWithCost.first].getBestCity(0 - cityWithCost.second, thisIndex); if (bestFromNeighbour.second > result.second) result = bestFromNeighbour; } return result.first; } pair<int, long long> City::getBestCity(long long currentProfit, int from) { pair<int, long long> result(thisIndex, currentProfit + profit); for (auto& cityWithCost : costs) { if (cityWithCost.first != from) { auto bestFromNeighbour = cities[cityWithCost.first].getBestCity(currentProfit - cityWithCost.second, thisIndex); if (bestFromNeighbour.second > result.second || (bestFromNeighbour.second == result.second && bestFromNeighbour.first < result.first)) result = bestFromNeighbour; } } return result; } int main() { ios_base::sync_with_stdio(false); for (int i = 0; i < 100010; ++i) { cities[i].thisIndex = i; } int cityCount, dayCount; cin >> cityCount >> dayCount; for (int i = 1; i <= cityCount; ++i) { int tmpProfit; cin >> tmpProfit; cities[i].profit = tmpProfit; } for (int path = 0; path < cityCount-1; ++path) { int tmpA, tmpB; long long tmpC; cin >> tmpA >> tmpB >> tmpC; cities[tmpA].costs[tmpB] = tmpC; cities[tmpB].costs[tmpA] = tmpC; } int currentCityIndex = 1; for (int day = 0; day < dayCount; ++day) { int changeType; cin >> changeType; if (changeType == 1) { int cityIndex; long long newProfit; cin >> cityIndex >> newProfit; cities[cityIndex].profit = newProfit; } else { int cityA, cityB; long long newCost; cin >> cityA >> cityB >> newCost; cities[cityA].costs[cityB] = newCost; cities[cityB].costs[cityA] = newCost; } currentCityIndex = cities[currentCityIndex].getBestCity(); cout << currentCityIndex << ' '; } } |