#include "dreaming.h" #include<bits/stdc++.h> using namespace std; vector<array<int, 2>> ad[100005]; int dis[100005], curmin = 0, curmax = 0; bool visited[100005]; void dfs(int u) { visited[u] = 1; dis[u] = 0; for(auto &[v, d] : ad[u]) if(visited[v] == 0){ dfs(v); dis[u] = max(dis[u], dis[v] + d); } visited[u] = 0; } void reroot(int u) { visited[u] = 1; pair<int, int> bestval = {0, 0}; for(auto &[v, d] : ad[u]){ if(bestval.second < dis[v]+d) bestval.second = dis[v]+d; if(bestval.first < bestval.second) swap(bestval.first, bestval.second); } dis[u] = bestval.first; //cerr<<"A"<<u<<" "<<dis[u]<<endl; curmin = min(curmin, dis[u]); curmax = max(curmax, bestval.first + bestval.second); for(auto &[v, d] : ad[u]) if(visited[v] == 0){ int re = dis[u]; if(dis[v] + d == bestval.first) dis[u] = bestval.second; reroot(v); dis[u] = re; } } int travelTime(int n, int m, int l, int A[], int B[], int T[]) { for(int i = 0; i < m; i++){ int u = A[i], v = B[i], d = T[i]; ad[u].push_back({v, d}); ad[v].push_back({u, d}); } vector<int> a; for(int i = 0; i < n; i++) if(visited[i] == 0){ curmin = 1e18; dfs(i); reroot(i); a.push_back(curmin); } sort(a.begin(), a.end(), greater<int>()); int ans = 0; if(a.size() >= 2) ans = max(ans, a[0] + a[1] + l); if(a.size() >= 3) ans = max(ans, a[1] + a[2] + 2*l); return max(ans, curmax); }

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:41:18: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   41 |         curmin = 1e18; dfs(i);
      |                  ^~~~