| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1122649 | Newtonabc | 꿈 (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include "dreaming.h"
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
//n-m component
const int N=1e5+10;
bool vs[N];
int n,m,l,dist[N],cp,dista[N],distb[N];
queue<int> q;
vector<pair<int,int> > adj[N];
vector<int> com[N];
int tmp;
void bfs(int st,int *d,int type){
for(int i=0;i<com[type].size();i++) vs[com[type][i]]=false;
d[st]=0;
vs[st]=true;
q.push(st);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i].second;
int w=adj[u][i].first;
if(vs[v]) continue;
d[v]=d[u]+w;
vs[v]=true;
q.push(v);
}
}
}
int longnode(int st,int type,int sp=1){
int mx,mxval=-1;
for(int i=0;i<com[type].size();i++) vs[com[type][i]]=false;
dist[st]=0;
vs[st]=true;
q.push(st);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i].second;
int w=adj[u][i].first;
if(vs[v]) continue;
dist[v]=dist[u]+w;
vs[v]=true;
q.push(v);
}
}
for(int i=0;i<com[type].size();i++){
if(dist[com[type][i]]>mxval){
mxval=dist[com[type][i]];
mx=com[type][i];
}
}
if(sp==2) tmp=mxval;
return mx;
}
void bfscom(int st){
vs[st]=true;
q.push(st);
com[cp].push_back(st);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i].second;
int w=adj[u][i].first;
if(vs[v]) continue;
com[cp].push_back(v);
vs[v]=true;
q.push(v);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N,m=M,l=L;
int ans=0;
int mx,mxval;
for(int i=0;i<m;i++){
adj[A[i]].push_back(mp(T[i],B[i]));
adj[B[i]].push_back(mp(T[i],A[i]));
}
for(int i=0;i<n;i++){
if(vs[i]) continue;
cp++;
bfscom(i);
}
vector<int> v;
for(int i=1;i<=cp;i++){
if(com[i].size()==1){
v.push_back(0);
continue;
}
int u=com[i][0];
int a=longnode(u,i);
int b=longnode(a,i,2);
ans=max(ans,tmp);
bfs(a,dista,i);
bfs(b,distb,i);
int mnmax=INT_MAX;
//cout<<u <<" " <<a <<" " <<b <<"\n";
for(int j=0;j<com[i].size();j++){
//cout<<com[i][j] <<" " <<dista[com[i][j]] <<" " <<distb[com[i][j]] <<"\n";
mnmax=min(max(dista[com[i][j]],distb[com[i][j]]),mnmax);
}
//cout<<mnmax <<"\n\n";
v.push_back(mnmax);
}
sort(v.begin(),v.end(),greater<int>());
if(v.size()>=2) ans=max(ans,v[0]+v[1]+l);
if(v.size()>=3) ans=max(ans,v[1]+v[2]+2*l);
return ans;
}
int tmpa[N],tmpb[N],tmpt[N];
int main(){
int n,m,l;
cin>>n >>m >>l;
for(int i=0;i<m;i++){
cin>>tmpa[i] >>tmpb[i] >> tmpt[i];
}
cout<<travelTime(n,m,l,tmpa,tmpb,tmpt);
}