| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1207819 | orcslop | Dreaming (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 0
#define dbgn(...) 0
#endif
const int INF = 1e9;
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
freopen("dreaming.in", "r", stdin);
int n, m, l;
cin >> n >> m >> l;
vector<vector<pair<int, int>>> adj(n);
for(int i = 0; i < m; i++){
int a, b, t;
cin >> a >> b >> t;
adj[a].push_back({b, t});
adj[b].push_back({a, t});
}
vector<int> cc_time;
auto dijkstra = [&](int start_node) {
vector<int> dist(n, INF);
if (start_node >= 0 && start_node < n) {
dist[start_node] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start_node});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (auto& edge : adj[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
}
return dist;
};
vector<bool> vis(n, false);
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
vector<int> ccn;
queue<int> q;
q.push(i);
vis[i] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
ccn.push_back(u);
for (auto& edge : adj[u]) {
int v = edge.first;
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
if (ccn.size() <= 1) {
cc_time.push_back(0);
continue;
}
vector<int> st_dist = dijkstra(i);
int endpoint_a = -1;
int max_dist = -1;
for (int node : ccn) {
if (st_dist[node] != INF && st_dist[node] > max_dist) {
max_dist = st_dist[node];
endpoint_a = node;
}
}
vector<int> a_dist = dijkstra(endpoint_a);
int endpoint_b = -1;
max_dist = -1;
for (int node : ccn) {
if (a_dist[node] != INF && a_dist[node] > max_dist) {
max_dist = a_dist[node];
endpoint_b = node;
}
}
vector<int> b_dist = dijkstra(endpoint_b);
int c = INF;
for (int node : ccn) {
int e = max(a_dist[node], b_dist[node]);
if (e < c) {
c = e;
}
}
cc_time.push_back(c);
}
}
sort(cc_time.begin(), cc_time.end(), greater());
int ans = cc_time[0];
if(cc_time.size() >= 2) ans = max(ans, cc_time[0] + cc_time[1] + l);
if(cc_time.size() >= 3) ans = max(ans, cc_time[1] + cc_time[2] + 2 * l);
cout << ans << '\n';
return 0;
}