Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <assert.h>
- #include <unordered_map>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef vector < long long > vll;
- typedef pair < long long, long long > pll;
- typedef pair < int, int > pii;
- typedef vector < int > vii;
- #define csl ios_base::sync_with_stdio(false); cin.tie(NULL)
- #define l(x) (((x) << 1) | 1)
- #define r(x) ((l(x)) + 1)
- #define mp make_pair
- #define fst first
- #define snd second
- ll t, n, u, v, m, q, r, ql, qr, k, l, s, x, y, w, c;
- const int N = 1e5 + 500;
- const long long mod = 1e9 + 7;
- const long long INF = 1LL << 57LL;
- const bool JUDGE = false;
- vii adj[N];
- bool vis[N];
- vii cst[N];
- ll P[N];
- ll deepest[N];
- ll deep[N];
- ll dp[N];
- ll len[N];
- ll D[N];
- multiset < ll > A[N];
- ll ans = 0;
- vll cv;
- void dfs(int v, int p, int dep) {
- D[v] = dep;
- P[v] = p;
- deepest[v] = 0;
- vis[v] = true;
- for (int i = 0; i < adj[v].size(); ++i) {
- int u = adj[v][i];
- if (u == p) continue;
- dfs(u, v, dep + cst[v][i]);
- ll x = deepest[u] + cst[v][i];
- if (x > deepest[v]) swap(deepest[v], x);
- if (deep[v] < x) deep[v] = x;
- A[v].insert(deepest[u] + cst[v][i]);
- len[u] = cst[v][i];
- }
- ans = max(ans, deepest[v] + deep[v]);
- cv.push_back(v);
- }
- ll lm;
- int up(int v) {
- if (P[v] == -1) {
- return 0;
- }
- if (dp[v] != -1) return dp[v];
- ll & ret = dp[v];
- ret = up(P[v]) + len[v];
- A[P[v]].erase(A[P[v]].find(deepest[v] + len[v]));
- if (A[P[v]].size()) ret = max(ret, *A[P[v]].rbegin() + len[v]);
- A[P[v]].insert(deepest[v] + len[v]);
- return ret;
- }
- vll R;
- int main(){
- csl;
- if (JUDGE) {
- freopen("in.txt", "r", stdin);
- freopen("out.txt", "w", stdout);
- }
- cin >> n >> m >> l;
- memset(dp, -1, sizeof(dp));
- memset(P, -1, sizeof(P));
- for (int i = 0; i < m; ++i) {
- cin >> u >> v >> c;
- adj[u].push_back(v);
- adj[v].push_back(u);
- cst[u].push_back(c);
- cst[v].push_back(c);
- }
- for (int i = 0; i < n; ++i) {
- if (vis[i]) continue;
- cv.clear();
- lm = INF;
- dfs(i, -1, 0);
- for (int j = 0; j < cv.size(); ++j) {
- up(cv[j]);
- }
- for (int j = 0; j < cv.size(); ++j) {
- lm = min(lm, max(dp[cv[j]], deepest[cv[j]]));
- }
- R.push_back(lm);
- }
- sort(R.begin(), R.end());
- reverse(R.begin(), R.end());
- if (R.size() == 1);
- //cout << ans << '\n';
- /*for (int i = 0; i < R.size(); ++i) {
- cout << R[i] << " ";
- }cout << '\n';*/
- if (R.size() >= 2) {
- ans = max(ans, R[0] + R[1] + l);
- //cout << ans << '\n';
- }
- if (R.size() >= 3) {
- ans = max(ans, R[1] + R[2] + l * 2LL);
- //cout << ans << '\n';
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement