#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define trace(x) cerr << #x << " " << x << endl
const int N = 1e5+11;
int n, m, l;
vector <pair <int, int> > ls[N];
int bio[N];
pair <int, int> maxi;
pair <int, int> mama[N];
int res = 0;
vector <int> v;
void dfs (int x, int dalj) {
bio[x] = 1;
maxi = max(maxi, mp(dalj, x));
for (int i=0;i<ls[x].size();i++) {
if (bio[ls[x][i].ff]) continue;
dfs(ls[x][i].ff, dalj + ls[x][i].ss);
}
}
void dfss (int x, int p, int dalj) {
maxi = max(maxi, mp(dalj, x));
mama[x].ff = p;
for (int i=0;i<ls[x].size();i++) {
if (ls[x][i].ff == p) {
mama[x].ss = ls[x][i].ss;
continue;
}
dfss (ls[x][i].ff, x, dalj+ls[x][i].ss);
}
}
int gore (int x, int dalj, int dm) {
int ret = max(dalj, dm-dalj);
if (mama[x].ff == -1) return ret;
ret = min(ret, gore (mama[x].ff, dalj+mama[x].ss, dm));
return ret;
}
int main() {
cin >> n >> m >> l;
for (int i=0;i<m;i++) {
int a1, a2, a3;
scanf("%d%d%d", &a1, &a2, &a3);
ls[a1].pb(mp(a2, a3));
ls[a2].pb(mp(a1, a3));
}
for (int i=0;i<n;i++) {
maxi = mp(0, 0);
if (bio[i]) continue;
dfs(i, 0);
int x = maxi.ss;
maxi = mp(0, 0);
dfss(x, -1, 0);
int y = maxi.ss;
int dm = maxi.ff;
res = max(res, dm);
v.pb(gore(y, 0, dm));
}
sort (v.begin(), v.end());
int s = v.size();
if (s >= 2) {
res = max(res, v[s-1]+v[s-2]+l);
}
if (s >= 3) {
res = max(res, v[s-2]+v[s-3]+2*l);
}
cout << res;
return 0;
}
Compilation message
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<ls[x].size();i++) {
~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfss(int, int, int)':
dreaming.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<ls[x].size();i++) {
~^~~~~~~~~~~~~
dreaming.cpp: In function 'int main()':
dreaming.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a1, &a2, &a3);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/cc7TVCWa.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc6I68I5.o:grader.c:(.text.startup+0x0): first defined here
/tmp/cc6I68I5.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
