#include <bits/stdc++.h> #include"dreaming.h" #define rep(i, a, b) for (int i = (a); i < (b); i++) #define per(i, a, b) for(int i = (a); i > (b); i--) #define ll long long #define pb push_back #define xx first #define yy second #define pb push_back #define pii pair<int,int> #define vi vector<int> #define vpii vector<pii> using namespace std; constexpr bool DEG = 0; #define DEBUG if(DEG) constexpr int N = 1e5+7; vpii graf[N]; pii sred[N]; int par[N], odl[N],drugi, R, n,m,l; int Find(int v){ if(par[v] == v) return v; return par[v] = Find(par[v]); } pii f(pii a, pii b){ int sa = a.xx + a.yy; int sb = b.xx + b.yy; if(sa < sb) return a; if(sa > sb) return b; if(a.xx < b.xx) return a; return b; } pii f2(pii a, pii b){ int sa = a.xx + a.yy; int sb = b.xx + b.yy; if(sa > sb) return a; if(sa < sb) return b; if(a.xx < b.xx) return a; return b; } void Union(int a, int b){ a = Find(a); b = Find(b); if(a == b) return; par[b] = a; pii w1 = {sred[a].xx + l, sred[b].xx}; if(w1.xx < w1.yy) swap(w1.xx, w1.yy); pii w2 = {sred[a].xx, sred[b].xx + l}; if(w2.xx < w2.yy) swap(w2.xx, w2.yy); pii w = f(w1, w2); pii s = f2(sred[a], sred[b]); int sw = w.xx + w.yy; int ss = s.xx + s.yy; if(ss > sw) sred[a] = s; else if(ss == sw){ if(s.xx < w.xx) sred[a] = s; else sred[a] = w; } else sred[a] = w; } int dfs(int v, int p){ int maxx = v; for(auto i : graf[v]){ if(i.yy == p) continue; odl[i.yy] = odl[v] + i.xx; int c = dfs(i.yy, v); if(odl[maxx] < odl[c]){ maxx = c; } Union(v,i.yy); } return maxx; } int countsred(int v, int p){ int czy = (v == drugi); for(auto i : graf[v]){ if(i.yy == p) continue; czy |= countsred(i.yy, v); } if(czy == 0) return 0; pii xd = {odl[drugi] - odl[v], odl[v]}; if(xd.xx < xd.yy) swap(xd.xx, xd.yy); if(xd.xx < sred[R].xx) sred[R] = xd; return 1; } // int travelTime(int N,int M,int L, vi A, vi B, vi T){ int travelTime(int N,int M,int L, int A[], int B[], int T[]){ n = N; m = M; l = L; rep(i,0,m){ graf[A[i]+1].pb({T[i], B[i]+1}); graf[B[i]+1].pb({T[i], A[i]+1}); } rep(v,1,n+1) par[v] = v, odl[v] = -1; rep(i,1,n+1){ if(odl[i] == -1){ odl[i] = 0; int c = dfs(i, 0); odl[c] = 0; drugi = dfs(c, 0); R = Find(i); sred[R] = {odl[drugi], 0}; countsred(c, 0); } } rep(i,1,n) Union(i,i+1); int w = Find(1); int wynik = sred[w].xx + sred[w].yy; return wynik; } /* int main(){ int n1,m1,l1; cin>>n1>>m1>>l1; vi a,b,c; rep(i,0,m1){ int x,y,z; cin>>x>>y>>z; a.pb(x); b.pb(y); c.pb(z); } cout<<travelTime(n1,m1,l1,a,b,c)<<"\n"; } /* 12 8 2 0 1 4 1 2 2 2 3 4 5 6 3 6 7 7 7 8 5 9 10 3 11 7 1 5 2 100 0 1 8 3 4 4 */