| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1317124 | electron31 | Dreaming (IOI13_dreaming) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
namespace std {
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int N, M, L; cin >> N >> M >> L;
vector<vector<pair<int, int>>> adj(N);
for(int i = 0;i < M; ++i){
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<bool> vis(N, false);
vector<int> A;
auto dfs1 = y_combinator([&] (auto &&self, int s, int e, vector<int>& D) -> void{
for(auto &[u, d]: adj[s]){
if(u != e){
vis[u] = true;
D[u] = D[s] + d;
self(u, s, D);
}
}
});
auto dfs2 = y_combinator([&] (auto &&self, int s, int e, vector<int> &D, vector<int> &H, int& mn) -> void{
for(auto &[u, d]: adj[s]){
if(u != e){
D[u] = D[s] + d;
self(u, s, D, H, mn);
H[s] = H[u] + d;
mn = min(mn, max(H[s], D[s]));
}
}
});
for(int i = 0;i < N; ++i){
if(vis[i]) continue;
vis[i] = true;
vector<int> D(N, -1);
D[i] = 0;
dfs1(i, -1, D);
int mx = 0, S = i;
for(int j = 0;j < N; ++j){
if(D[j] > mx){
mx = D[j];
S = j;
}
}
if(S == i) continue;
D = vector<int> (N, -1);
vector<int> H(N, 0);
H[S] = 0; D[S] = 0;
int mn = 1e9;
dfs2(S, -1, D, H, mn);
A.push_back(mn);
}
sort(A.rbegin(), A.rend());
if(A.size() == 1){
cout << A[0] << "\n";
}
else{
cout << A[0] + A[1] + L << "\n";
}
}