#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define coc g[node][i].st
#define yol g[node][i].nd
#define inf 1000000007
#define N 1000005
using namespace std;
typedef pair < int , int > ii;
// #include "dreaming.h"
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
int dp[N], u[N], k;
ii c[N];
ii mn, mx;
vector < ii > g[N];
void hazirla(int node, int par){
for(int i = 0; i < g[node].size(); i++){
if(coc == par)
continue;
hazirla(coc, node);
dp[node] = max(dp[node], dp[coc] + yol);
}
}
void dfs(int node, int us){
u[node] = 1;
mn = min(mn, mp(max(us, dp[node]), node) );
multiset < int > s;
s.insert(0);
for(int i = 0; i < g[node].size(); i++){
if(u[coc])
continue;
s.insert(dp[coc] + yol);
}
for(int i = 0; i < g[node].size(); i++){
if(u[coc])
continue;
s.erase(s.find(dp[coc] + yol));
dfs(coc, max(us + yol, *s.rbegin() + yol));
s.insert(dp[coc] + yol);
}
}
void bul(int node, int par, int yoll){
mx = max(mx, mp(yoll, node));
for(int i = 0; i < g[node].size(); i++)
if(coc != par)
bul(coc, node, yoll + yol);
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i = 0; i < m; i++){
a[i]++;b[i]++;
g[a[i]].pb(mp(b[i], t[i]));
g[b[i]].pb(mp(a[i], t[i]));
}
// multiset < int > s;
for(int i = 1; i <= n; i++)
if(!u[i]){
mn.st = inf;
hazirla(i, 0);
dfs(i, 0);
c[++k] = mn;
// cout << mn.st << " " << mn.nd << endl;
}
sort(c + 1, c + k + 1);
for(int i = 1; i < k; i++){
g[c[i].nd].pb(mp(c[k].nd, l));
g[c[k].nd].pb(mp(c[i].nd, l));
// cout << "AMK" << k << "AMK" << endl;
}
mx = mp(-inf, 0);
bul(1, 0, 0);
int git = mx.nd;
mx = mp(-inf, 0);
bul(git, 0, 0);
return mx.st;
}
#define MAX_N 100000
static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int nnn, M, L, i;
int res;
res = scanf("%d%d%d", &nnn, &M, &L);
for (i = 0; i < M; i++)
res = scanf("%d%d%d", &A[i], &B[i], &T[i]);
int answer = travelTime(nnn, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}
Compilation message
dreaming.cpp: In function 'void hazirla(int, int)':
dreaming.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++){
~~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++){
~~^~~~~~~~~~~~~~~~
dreaming.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++){
~~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void bul(int, int, int)':
dreaming.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int main()':
dreaming.cpp:100:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
/tmp/ccnJI4ZP.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccyaWdWy.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccyaWdWy.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
