#include <bits/stdc++.h>
#include <dreaming.h>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll ;
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef priority_queue< int, vector <int> , greater<int> > spq;
const int NN = 1e5+5 ;
vpi adj[NN] ;
int dp1[NN],dp2 [NN] ;
bool visited[NN] ;
int Min ;
void max2(int& a , int& b , int x ){
if( x < b) return ;
if( x > a ){
b = a ;
a = x ;
return ;
}
if( x > b && x < a ){
b = x ;
}
}
void dfs(int u , int p){
int v , w;
visited[u] = 1 ;
for(pi pr : adj[u] ){
v = pr.fi ;
w = pr.se ;
if( v != p ){
dfs(v,u) ;
max2(dp1[u],dp2[u],w+dp1[v]);
}
}
}
void dfs0(int u , int p ){
// cout << u << " " << dp1[u] << " " << dp2[u]<<endl ;
for(pi v : adj[u]){
if( v.fi != p )
dfs0(v.fi,u) ;
}
}
void dfs1(int u , int p ){
int w , v ;
for(pi pr : adj[u] ){
v = pr.fi ;
w = pr.se ;
if( v != p ){
if( dp1[u] != dp1[v]+w){
max2(dp1[v],dp2[v],dp1[u]+w );
}
// if( dp2[u] != dp2[v]+w) {
else max2(dp1[v],dp2[v],dp2[u]+w );
dfs1(v,u) ;
}
}
Min = min(Min,dp1[u]) ;
}
void edge(int u , int v , int w ){
adj[u].pb({v,w}) ;
}
int travelTime(int N,int M,int L ,int A[],int B[],int T[]){
for(int i = 0 ; i < M ; i++ ){
edge(A[i],B[i],T[i]) ;
edge(B[i],A[i],T[i]) ;
}
priority_queue<int> q;
for(int i = 0 ; i < N ; i++ ){
if( !visited[i]){
Min= 1e9 ;
dfs(i,-1);
dfs1(i,-1);
dfs0(i,-1) ;
q.push(Min) ;
}
}
Min = q.top() ; q.pop() ;
// cout << Min << " " << q.top() << endl;
return L+Min+q.top();
}
int main(){
ifstream cin("in.in");
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 << travelTime(n,m,l,a,b,t) << endl;
}
Compilation message
/tmp/ccXzaeeJ.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccfVl9Zb.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
