| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 694744 | hgmhc | 꿈 (IOI13_dreaming) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// 디버깅 오래 걸린 이유 및 반성:
// 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);
}