#include "dreaming.h" #include <algorithm> #include <iostream> #include <queue> #include <utility> #include <vector> #include <map> using namespace std; #define pb push_back long long a, b, c, d, h, n, m, x, y; map<pair<int, int>, int> weight; vector<int> adj[1000000]; vector<bool> vis(1000000); vector<int> par(1000000); long long maxdist; vector<int> component; void dfs(int node, long long dist) { vis[node] = 1; component.pb(node); if(dist > maxdist) { maxdist = dist; h = node; } for(auto j : adj[node]) { if(!vis[j]) { par[j] = node; dfs(j, dist+weight[{node, j}]); } } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for(int i = 0; i<M; i++) { adj[A[i]].pb(B[i]); adj[B[i]].pb(A[i]); weight[{A[i], B[i]}] = T[i]; weight[{B[i], A[i]}] = T[i]; } vector<long long> all; long long ans = 0; for(int i = 0; i<N; i++) { if(!vis[i]) { // cout << i << " "; h = i; maxdist = 0; component.clear(); dfs(i, 0); for(auto j : component) { par[j] = 0; vis[j] = 0; } maxdist = 0; x = h; component.clear(); dfs(x, 0); vector<int> path; long long tt = 0; while(h != x) { path.pb(weight[{h, par[h]}]); tt += weight[{h, par[h]}]; h = par[h]; } y = 100000000000000000; h = 0; for(int j = 0; j<path.size(); j++) { h += path[j]; y = min(y, (long long)max(h, tt-h)); } ans = max(ans, tt); // cout << y << "\n"; if(y==100000000000000000) { all.pb(0); } else all.pb(y); } } sort(all.rbegin(), all.rend()); if(all.size()==1) { return ans; } // for(auto j : all) cout << j << " "; ans = max(ans, all[0] + all[1] + L); if(all.size() > 2) { ans = max(ans, all[1]+all[2]+L+L); } return ans; } // int32_t main() { // ios::sync_with_stdio(false); // cout.tie(0); cin.tie(0); // int n, m, l; // cin >> n >> m >> l; // int A[m], B[m], C[m]; // for(int i = 0; i<m; i++) { // cin >> A[i] >> B[i] >> C[i]; // } // cout << travelTime(n, m, l, A, B, C); // return 0; // }