// 디버깅 오래 걸린 이유 및 반성:
// tree dp에서는 visited를 잘 검사하더라도 부모 노드로 다시 올라가는 경우가 없도록 e를 항상 설정해주도록 하자.
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define dbg(x) cerr << #x << ": " << x << '\n'
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
const int N = 1e5+3, M = N;
int n, m, l;
ll dp[N];
vector<ii> adj[N];
bool vis[N];
void dfs1(int s, int e = 0) {
for (auto [u,w] : adj[s]) if (u != e) {
dfs1(u,s), Mup(dp[s],dp[u]+w);
}
}
ll x, ans;
void dfs2(int s, int e = 0, ll v = 0) {
if (vis[s]) return;
vis[s] = true;
ll mx1 = 0, mx2 = 0;
int fr = 0;
for (auto [u,w] : adj[s]) if (u != e) {
if (mx1 < dp[u]+w) {
mx2 = mx1;
mx1 = dp[u]+w, fr = u;
} else if (mx2 < dp[u]+w) {
mx2 = dp[u]+w;
}
}
Mup(dp[s],v);
mup(x,dp[s]);
Mup(ans,dp[s]);
for (auto [u,w] : adj[s]) if (u != e) {
if (fr != u) dfs2(u,s,max(v,mx1)+w);
else dfs2(u,s,max(v,mx2)+w);
}
}
int main() {
scanf("%d %d %d", &n, &m, &l);
rep(i,1,m) {
int a, b, t;
scanf("%d %d %d", &a, &b, &t);
adj[a].push_back({b,t});
adj[b].push_back({a,t});
}
vector<ll> v;
rep(i,0,n-1) if (not vis[i]) {
x = 1e18, dfs1(i), dfs2(i);
v.push_back(x);
}
sort(v.rbegin(),v.rend());
if (siz(v) == 1) Mup(ans,v[0]);
else if (siz(v) == 2) Mup(ans,v[0]+l+v[1]);
else Mup(ans,max(v[0]+l+v[1],v[1]+l+l+v[2]));
printf("%lld", ans);
}
Compilation message
dreaming.cpp: In function 'int main()':
dreaming.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d %d %d", &n, &m, &l);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d %d %d", &a, &b, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccyGbY9x.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccv9hCIx.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccv9hCIx.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
