voidDP(){ ll now = 0, mx = 0; for (int i = 1; i <= tot; i++) { bef[i] = max(bef[i-1], now + Mx[i]); if (i > 1) bef2[i] = max(bef2[i-1], mx + now + Mx[i]); mx = max(mx, Mx[i] - now); now += len[i]; } now = mx = 0; for (int i = tot; i; i--) { aft[i] = max(aft[i+1], now + Mx[i]); if (i < tot) aft2[i] = max(aft2[i+1], mx + now + Mx[i]); mx = max(mx, Mx[i] - now); now += len[i-1]; } Ans = min(Ans, bef2[tot]); for (int i = 1; i < tot; i++) { ll ccf = max(max(bef2[i], aft2[i+1]), bef[i] + aft[i+1] + len[tot]); ccf = max(ccf, ans); Ans = min(Ans, ccf); } }
intmain(){ read(n); Ans = 114514114514114514; for (int i = 1; i <= n; i++) { int u, v; ll w; read(u); read(v); read(w); addedge(u, v, w); } getcir(1, 0); for (int i = 1; i <= tot; i++) onc[c[i]] = 1; for (int i = 1; i <= tot; i++) { int x = c[i]; for (E(j)) if (to[j] == c[i%tot+1]) len[i] = val[j]; } for (int i = 1; i <= tot; i++) { solve(i); } DP(); printf("%.1lf\n", Ans / 2.0); return0; }