#include <bits/stdc++.h>
#include "dreaming.h"
#define fi first
#define se second
#define TASK "file"
using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
return 42;
}
int n, m, k;
int res;
int g[N];
int f[2][N];
vector<int> gNew[N];
vector<pair<int, int>> adj[N];
vector<pair<int, int>> center_node;
pair<int, int> center;
void load_tree(void) {
cin >> n >> m >> k;
for (int i = 1; i <= m; i ++) {
int u, v, w;
cin >> u >> v >> w;
u ++; v ++;
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
}
void dfs1(int u, int p) {
for (pair<int, int> v: adj[u]) if (v.fi != p) {
dfs1(v.fi, u);
if (f[0][u] <= f[0][v.fi] + v.se) {
f[1][u] = f[0][u];
f[0][u] = f[0][v.fi] + v.se;
} else
maximize(f[1][u], f[0][v.fi] + v.se);
}
}
void dfs2(int u, int p, int dist) {
g[u] = dist;
for (pair<int, int> v: adj[u]) if (v.fi != p) {
if (f[0][u] == f[0][v.fi] + v.se)
dfs2(v.fi, u, max(dist, f[1][u]) + v.se);
else
dfs2(v.fi, u, max(dist, f[0][u]) + v.se);
}
minimize(center, make_pair(max(dist, f[0][u]), u));
}
void dfs(int u, int p) {
for (pair<int, int> v: adj[u]) if (v.fi != p) {
dfs(v.fi, u);
if (f[0][u] <= f[0][v.fi] + v.se) {
f[1][u] = f[0][u];
f[0][u] = f[0][v.fi] + v.se;
} else
maximize(f[1][u], f[0][v.fi] + v.se);
}
maximize(res, f[0][u] + f[1][u]);
}
void solve(void) {
memset(g, -1, sizeof g);
for (int i = 1; i <= n; i ++) if (g[i] < 0) {
dfs1(i, i);
center = make_pair(INF, 0);
dfs2(i, i, 0);
center_node.push_back(center);
}
sort(center_node.begin(), center_node.end(), greater<pair<int, int>>());
for (int i = 1; i < center_node.size(); i ++) {
adj[center_node[0].se].push_back(make_pair(center_node[i].se, k));
adj[center_node[i].se].push_back(make_pair(center_node[0].se, k));
}
res = 0;
memset(f, 0, sizeof f);
dfs(1, 1);
cout << res;
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0);
int test = 1;
// cin >> test;
while (test --) {
load_tree();
solve();
}
return 0;
}
Compilation message
dreaming.cpp: In function 'void solve()':
dreaming.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i = 1; i < center_node.size(); i ++) {
| ~~^~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccDROrcf.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc41a1tf.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
