#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>> al(100005);
vector<tuple<int,int,int>> dist(100005, {1e9, -1, 0});
// dist, previous node, previous edge weight
vector<bool> vis(100005);
vector<int> curtree;
vector<int> guys;
void dfs(int cur, pair<int,int> pre){
vis[cur]=true;
curtree.push_back(cur);
for(auto [to, cost]:al[cur]){
//~ printf("at %d, to %d, cost %d\n", cur, to, cost);
if(vis[to])continue;
get<0>(dist[to])=get<0>(dist[cur])+cost;
get<1>(dist[to])=cur;
get<2>(dist[to])=cost;
dfs(to, {cur, cost});
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<M;i++){
al[A[i]].push_back({B[i], T[i]});
al[B[i]].push_back({A[i],T[i]});
}
int x, y;
for(int i=0;i<N;i++){
if(vis[i])continue;
dist[i]={0, -1, 0};
dfs(i, {-1, 0});
x=i;
for(auto node : curtree){
if(get<0>(dist[node])>get<0>(dist[x])){
x=node;
}
}
for(auto node : curtree){
dist[node]={1e9, -1, 0};
vis[node]=false;
}
curtree.clear();
dist[x]={0, -1, 0};
dfs(x, {-1, 0});
y=x;
for(auto node : curtree){
if(get<0>(dist[node])>get<0>(dist[y])){
y=node;
}
}
curtree.clear();
int dl=get<0>(dist[y]);
vector<pair<int,int>> dia;
int cur=y;
while(get<1>(dist[cur]) != -1){
dia.push_back({get<1>(dist[cur]), get<2>(dist[cur])});
cur=get<1>(dist[cur]);
}
int cv=dl, sm=0;
for(auto it: dia){
sm+=it.second;
cv=min(cv, max(sm, dl-sm));
}
//~ printf("i=%d, x %d, y %d, dl is %d, cv is %d\n",i,x,y,dl, cv);
guys.push_back(cv);
}
sort(guys.begin(),guys.end(), greater<int>());
return max(guys[0]+L+guys[1], guys[1]+2*L+guys[2]);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |