# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1276440 | avohado | 꿈 (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include"dreaming.h
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
vector<pair<int, int>> g[maxn];
bool a[maxn];
long long k;int i1;
int dfs(int u, int p){
if(g[u].size()==1){
return u;
}
for(auto i:g[u]){
if(i.f!=p){
return dfs(i.f, u);
}
}
}
long long dfs2(int u, int p, long long sum){
long long mn=0;
for(auto i:g[u]){
mn=max(mn, dfs2(i.f, u, sum+i.s));
}
if(max(mn, sum)<k){
i1=u;
k=max(mn, sum);
}
return mn;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i=0; i<m; i++){
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
vector<long long> v;
for(int i=0; i<m; i++){
if(!a[i]){
k=INT64_MAX;
u=dfs(i, i);
dfs2(u, u, 0);
v.push_back(k);
}
}
sort(v.begin(), v.end(), greater<>);
if(v.size()>2){
return v[0]+v[1]+L;
}else{
return max(v[0]+v[1]+L, v[1]+v[2]+L*2);
}
}
/*int main(){
cin.tie(nullptr)->sync_with_stdio(0);
int t=1;
cin >> t;
while(t--){
solve();
cout << "\n";
}
return 0;
}*/