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 #include #define f first #define s second #define MP make_pair #define PB push_back #define LL long long #define pii pair #define pll pair #define ALL(V) V.begin(),V.end() #define f1(a,b) for(int a=1;a<=b;a++) #define f0(a,b) for(int a=0;a q; LL n,a,b,c,d,qwe; LL wag[N],odw[N], ode[N]; map M; vector G[N]; int bfs(int); LL gemacht(int,int); int32_t main(void) { boost; cin>>n>>qwe; f1(i,n) { cin>>wag[i]; } wag[0]=-2e18; for(int i=1;i>a>>b>>c; G[a].PB(b); G[b].PB(a); if(a>b) swap(a,b); M[MP(a,b)]=c; } int akt=1; while(qwe--) { cin>>a>>b>>c; if(a==1) wag[b]=c; else { cin>>d; a=c; if(a>b) swap(a,b); M[MP(a,b)]=d; } akt=bfs(akt); cout<wag[maks]-ode[maks]) maks=v; if(v!=poc&&wag[v]-ode[v]==wag[maks]-ode[maks]) maks=min(maks,v); f0(i,G[v].size()) { int w=G[v][i]; if(odw[w]==1) continue; odw[w]=1; ode[w]=ode[v]+gemacht(w,v); q.push(w); } } return maks; } LL gemacht(int a, int b) { if(a>b) swap(a,b); return M[MP(a,b)]; }