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 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 #include #include #include #include #include #include #include #include using namespace std; #define INF LLONG_MAX // max price const int sz=100001; // max verticles vector > a[sz]; // adjacency list long long income[sz]; // income in cities long long dis[sz]; //shortest distance bool vis[sz]={0}; // if visited class prioritize { public: bool operator ()(pair&p1 ,pair&p2) { return p1.second>p2.second; } }; void Dijkstra(int source, int n) //Algorithm for SSSP { for(int i=0;i<=n;i++) { //Set initial distances to Infinity dis[i] = INF; vis[i] = 0; } priority_queue ,vector >, prioritize> pq; //Priority queue to store vertex,weight pairs pq.push(make_pair(source,dis[source]=0)); //Pushing the source with distance from itself as 0 while(!pq.empty()) { pair curr=pq.top(); //Current vertex. The shortest distance for this has been found pq.pop(); int cv=curr.first,cw=curr.second; //'cw' the final shortest distance for this vertex if(vis[cv]) { //If the vertex is already visited, no point in exploring adjacent vertices continue; } vis[cv]=true; for(int i=0;i 0) { double elapsed_secs = double(end - start) / CLOCKS_PER_SEC; start = end; cout << i << " Time: " << elapsed_secs << endl; } i++; } int main( ) { int n,q; scanf("%d %d", &n, &q); //cout << n << " " << q << endl; int m = n-1; // number of edges int x,y; long long w; //clock_t begin = clock(); for (int i = 1; i <= n; i++) { cin>>w; income[i] = w; } for (int i = 0;i < m;i++) { cin>>x>>y>>w; // vertex start, vertex end, weight of edge // cout << "(" << x << ", " << y << ") -> " << w << endl; a[x].push_back(make_pair(y,w)); a[y].push_back(make_pair(x,w)); } int currentCity = 1; // where we currently are for(int i = 0; i < q; i++) { cin>>x; if (x == 1) { cin >> y >> w; income[y] = w; } else if (x == 2) { cin >> x >> y >> w; bool found = false; for (int j = 0; j < a[x].size(); j++) { if(a[x][j].first == y) { a[x][j].second = w; found = true; break; } } if (!found) { a[x].push_back(make_pair(y,w)); } found = false; for (int j = 0; j < a[y].size(); j++) { if(a[y][j].first == x) { a[y][j].second = w; found = true; break; } } if (!found) { a[y].push_back(make_pair(x,w)); } } Dijkstra(currentCity,n); int maxCity = -1; long long maxProfit = LLONG_MIN; for(int j=1;j<=n;j++) { //cout << j << ":" << income[j] << " " << dis[j] << endl; if (currentCity !=j && income[j]-dis[j] > maxProfit) { maxCity = j; maxProfit = income[j]-dis[j]; //cout << "New max: [" << maxCity << " -> " << maxProfit << "]" << endl; } } currentCity = maxCity; if ( i > 0 ) { cout << " "; } cout << maxCity; //cout << " ###" << endl; } //cout << endl; //clock_t end = clock(); //double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; //cout << endl << "Time: " << elapsed_secs << endl; return 0; }