#include<iostream> #include<vector> using namespace std; struct wierzcholki{ vector <unsigned int> polaczenia; vector <unsigned int> koszt; bool odwiedzony; int cena; int wynik; }*w; int w_glab(int k, int suma) { w[k].odwiedzony = 1; for(int i=0; i<w[k].polaczenia.size(); i++) if(!w[w[k].polaczenia[i]].odwiedzony) { suma-=w[k].koszt[i]; if(w[0].wynik<=w[w[k].polaczenia[i]].cena+suma){ if (w[0].wynik==w[w[k].polaczenia[i]].cena+suma){ if (w[1].wynik>w[k].polaczenia[i]){ w[0].wynik=w[w[k].polaczenia[i]].cena+suma; w[1].wynik=w[k].polaczenia[i]; } } else{ w[0].wynik=w[w[k].polaczenia[i]].cena+suma; w[1].wynik=w[k].polaczenia[i]; } } w_glab(w[k].polaczenia[i],suma); suma+=w[k].koszt[i]; } } int main() { unsigned int n, pol, pocz, a, b, koszt,days; cin>>n; pol=n-1; pocz=1; cin>>days; w = new wierzcholki[n+1]; for (int i=1;i<=n;i++){ int x; cin>>x; w[i].cena=x; } for(int i=0; i<pol; i++){ cin>>a>>b>>koszt; w[a].polaczenia.push_back(b); w[a].koszt.push_back(koszt); w[b].polaczenia.push_back(a); w[b].koszt.push_back(koszt); } for (int j=0;j<days;j++){ int z,d; cin>>z; if (z==1){ cin>>a>>d; w[a].cena=d; } else { cin>>a>>b>>d; for(int i=0; i<w[a].polaczenia.size(); i++){ if (w[a].polaczenia[i]==b){ w[a].koszt[i]=d; break; } } for(int i=0; i<w[b].polaczenia.size(); i++){ if (w[b].polaczenia[i]==a){ w[b].koszt[i]=d; break; } } } w[0].wynik=w[w[pocz].polaczenia[0]].cena-w[pocz].koszt[0]; w[1].wynik=w[pocz].polaczenia[0]; w_glab(pocz,0); cout<<w[1].wynik<<" "; for(int i=1;i<=n;i++){ w[i].odwiedzony = 0; } pocz=w[1].wynik; } 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 | #include<iostream> #include<vector> using namespace std; struct wierzcholki{ vector <unsigned int> polaczenia; vector <unsigned int> koszt; bool odwiedzony; int cena; int wynik; }*w; int w_glab(int k, int suma) { w[k].odwiedzony = 1; for(int i=0; i<w[k].polaczenia.size(); i++) if(!w[w[k].polaczenia[i]].odwiedzony) { suma-=w[k].koszt[i]; if(w[0].wynik<=w[w[k].polaczenia[i]].cena+suma){ if (w[0].wynik==w[w[k].polaczenia[i]].cena+suma){ if (w[1].wynik>w[k].polaczenia[i]){ w[0].wynik=w[w[k].polaczenia[i]].cena+suma; w[1].wynik=w[k].polaczenia[i]; } } else{ w[0].wynik=w[w[k].polaczenia[i]].cena+suma; w[1].wynik=w[k].polaczenia[i]; } } w_glab(w[k].polaczenia[i],suma); suma+=w[k].koszt[i]; } } int main() { unsigned int n, pol, pocz, a, b, koszt,days; cin>>n; pol=n-1; pocz=1; cin>>days; w = new wierzcholki[n+1]; for (int i=1;i<=n;i++){ int x; cin>>x; w[i].cena=x; } for(int i=0; i<pol; i++){ cin>>a>>b>>koszt; w[a].polaczenia.push_back(b); w[a].koszt.push_back(koszt); w[b].polaczenia.push_back(a); w[b].koszt.push_back(koszt); } for (int j=0;j<days;j++){ int z,d; cin>>z; if (z==1){ cin>>a>>d; w[a].cena=d; } else { cin>>a>>b>>d; for(int i=0; i<w[a].polaczenia.size(); i++){ if (w[a].polaczenia[i]==b){ w[a].koszt[i]=d; break; } } for(int i=0; i<w[b].polaczenia.size(); i++){ if (w[b].polaczenia[i]==a){ w[b].koszt[i]=d; break; } } } w[0].wynik=w[w[pocz].polaczenia[0]].cena-w[pocz].koszt[0]; w[1].wynik=w[pocz].polaczenia[0]; w_glab(pocz,0); cout<<w[1].wynik<<" "; for(int i=1;i<=n;i++){ w[i].odwiedzony = 0; } pocz=w[1].wynik; } return 0; } |