| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1161912 | ty_mxzhn | 꿈 (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector < pair < int , int > > tree[N];
int vis[N] = {0};
for(int i = 0;i<M;i++){
tree[A[i]].push_back({B[i] , T[i]});
tree[B[i]].push_back({A[i] , T[i]});
}
// cout << "done1" << endl;
vector < int > vec;
for(int i = 0;i<N;i++){
if(vis[i] == 0){
// cout << "starting at : " << i << endl;
auto furthest = [&](int st){
map < int , int > visited;
priority_queue < pair < int , int > > pq;
pq.push({0,st});
pair < int , int > ret = {0,st};
while(!pq.empty()){
auto tmp = pq.top();
pq.pop();
if(visited[tmp.second])continue;
// cout << "visited : " << tmp.first << " " << tmp.second << endl;
visited[tmp.second] = 1;
ret = max(ret , {-tmp.first , tmp.second});
for(auto itr : tree[tmp.second]){
// cout << "pushing : " << tmp.first - itr.second << " , " << itr.first << endl;
pq.push({tmp.first - itr.second , itr.first});
}
}
return ret.second;
};
int node1 = furthest(i);
// cout << "NODE1 : " << node1 << endl;
int node2 = furthest(node1);
// cout << "NODE2 : " << node2 << endl;
// cout << "done3" << endl;
vector < int > path;
function<bool(int,int,int)> dfs = [&](int node , int par , int parcost){
// cout << "dfs : " << node << " " << par << " " << parcost << endl;
vis[node] = 1;
if(node == node2){
path.push_back(parcost);
return true;
}
bool bl = 0;
for(auto itr : tree[node]){
if(itr.first == par)continue;
// cout << node << " -> " << itr.first << endl;
if(dfs(itr.first,node,itr.second)){
path.push_back(parcost);
bl = 1;
}
}
return bl;
};
dfs(node1,node1,0);
// cout << "path : ";for(auto itr : path)cout << itr << " ";cout << endl;
// cout << "done4" << endl;
int sum = accumulate(all(path) , 0ll) , cursum = 0 , locans = sum;
for(int i = 0;i<sz(path);i++){
cursum += path[i];
locans = min(locans , max(cursum , sum-cursum));
}
// cout << "locans : " << locans << endl;
vec.push_back(locans);
}
}
sort(all(vec) , greater < int >{});
if(sz(vec) == 1)return vec[0];
else if(sz(vec) == 2)return vec[0] + vec[1] + L;
else return max(vec[0] + vec[1] + L , vec[1] + vec[2] + 2 * L);
}
signed main(){
int n,m,l;
cin >> n >> m >> l;
int a[m] , b[m] , t[m];
for(int i = 0;i<m;i++)cin >> a[i] >> b[i] >> t[i];
cout << "done" << endl;
int result = travelTime(n,m,l,a,b,t);
cout << "result : " << result << endl;
}