#include <iostream> #include <stdio.h> #include <limits.h> #include<bits/stdc++.h> # define INF 0x3f3f3f3f using namespace std; typedef pair<int, int> iPair; long long minDistance(long long dist[], bool sptSet[],long long V) { long long min = LLONG_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } int main() { long long V,liczba_dni; cin>>V; cin>>liczba_dni; int src=0,licznik=0; long long *miasta_profit=new long long[V]; list< pair<int, int> > *adj; adj = new list<iPair> [V]; for(int i=0;i<V;i++) { cin>>miasta_profit[i]; } for(int i=0;i<V-1;i++) { long long pom=0,pom1=0,pom2=0; cin>>pom; cin>>pom1; cin>>pom2; pom--; pom1--; adj[pom].push_back(make_pair(pom1, pom2)); adj[pom1].push_back(make_pair(pom, pom2)); } for(int d=0;d<liczba_dni;d++) { long long zmiana; cin>>zmiana; if(zmiana==1) { long long pom=0,pom1=0; cin>>pom; pom--; cin>>pom1; miasta_profit[pom]=pom1; } else { long long pom=0,pom1=0,pom2=0; cin>>pom; cin>>pom1; cin>>pom2; pom--; pom1--; adj[pom].push_back(make_pair(pom1, pom2)); adj[pom1].push_back(make_pair(pom, pom2)); } priority_queue< iPair, vector <iPair> , greater<iPair> > pq; vector<int> dist(V, INF); pq.push(make_pair(0, src)); dist[src] = 0; while (!pq.empty()) { int u = pq.top().second; pq.pop(); list< pair<int, int> >::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { int v = (*i).first; int weight = (*i).second; if (dist[v] > dist[u] + weight) { dist[v] = dist[u] + weight; pq.push(make_pair(dist[v], v)); } } } long long maxi=LLONG_MIN; int pom_na_wynik; for (int i = 0; i < V; i++) { if(src!=i) { if(miasta_profit[i]-dist[i]>maxi) { maxi=miasta_profit[i]-dist[i]; pom_na_wynik=i; } } } int wynik=pom_na_wynik; wynik++; cout<<wynik<<" "; src=pom_na_wynik; } return EXIT_SUCCESS; }
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 | #include <iostream> #include <stdio.h> #include <limits.h> #include<bits/stdc++.h> # define INF 0x3f3f3f3f using namespace std; typedef pair<int, int> iPair; long long minDistance(long long dist[], bool sptSet[],long long V) { long long min = LLONG_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } int main() { long long V,liczba_dni; cin>>V; cin>>liczba_dni; int src=0,licznik=0; long long *miasta_profit=new long long[V]; list< pair<int, int> > *adj; adj = new list<iPair> [V]; for(int i=0;i<V;i++) { cin>>miasta_profit[i]; } for(int i=0;i<V-1;i++) { long long pom=0,pom1=0,pom2=0; cin>>pom; cin>>pom1; cin>>pom2; pom--; pom1--; adj[pom].push_back(make_pair(pom1, pom2)); adj[pom1].push_back(make_pair(pom, pom2)); } for(int d=0;d<liczba_dni;d++) { long long zmiana; cin>>zmiana; if(zmiana==1) { long long pom=0,pom1=0; cin>>pom; pom--; cin>>pom1; miasta_profit[pom]=pom1; } else { long long pom=0,pom1=0,pom2=0; cin>>pom; cin>>pom1; cin>>pom2; pom--; pom1--; adj[pom].push_back(make_pair(pom1, pom2)); adj[pom1].push_back(make_pair(pom, pom2)); } priority_queue< iPair, vector <iPair> , greater<iPair> > pq; vector<int> dist(V, INF); pq.push(make_pair(0, src)); dist[src] = 0; while (!pq.empty()) { int u = pq.top().second; pq.pop(); list< pair<int, int> >::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { int v = (*i).first; int weight = (*i).second; if (dist[v] > dist[u] + weight) { dist[v] = dist[u] + weight; pq.push(make_pair(dist[v], v)); } } } long long maxi=LLONG_MIN; int pom_na_wynik; for (int i = 0; i < V; i++) { if(src!=i) { if(miasta_profit[i]-dist[i]>maxi) { maxi=miasta_profit[i]-dist[i]; pom_na_wynik=i; } } } int wynik=pom_na_wynik; wynik++; cout<<wynik<<" "; src=pom_na_wynik; } return EXIT_SUCCESS; } |