//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#include "dreaming.h"
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e5;
vector<pair<int, int> > Adj[N];
int dp[N], f[N], res;
bool visited[N];
void preDFS(int u, int p)
{
visited[u] = true;
for (auto x : Adj[u])
{
int v = x.first, w = x.second;
if (v == p)
{
continue;
}
preDFS(v, u);
dp[u] = max(dp[u], dp[v] + w);
}
}
int DFS(int u, int p)
{
int ret = max(f[u], dp[u]);
res = max(res, f[u] + dp[u]);
int t[2], id[2];
t[0] = t[1] = id[0] = id[1] = 0;
for (auto x : Adj[u])
{
int v = x.first, w = x.second;
if (v == p)
{
continue;
}
f[v] = f[u] + w;
for (int i = 1; i >= 0; -- i)
{
if (t[i] < dp[v] + w)
{
for (int j = 0; j < i; ++ j)
{
t[j] = t[j + 1];
id[j] = id[j + 1];
}
t[i] = dp[v] + w;
id[i] = v;
break;
}
}
}
for (auto x : Adj[u])
{
int v = x.first, w = x.second;
if (v == p)
{
continue;
}
for (int i = 1; i >= 0; -- i)
{
if (id[i] != v)
{
f[v] = max(f[v], t[i] + w);
break;
}
}
ret = min(ret, DFS(v, u));
}
return ret;
}
int travelTime(int n, int m, int l, vector<int> A, vector<int> B, vector<int> T)
{
for (int i = 0; i < m; ++ i)
{
int u = A[i], v = B[i];
Adj[u].push_back({v, T[i]});
Adj[v].push_back({u, T[i]});
}
int t[3];
t[0] = t[1] = t[2] = 0;
int cnt = 0;
for (int u = 0; u < n; ++ u)
{
if (!visited[u])
{
++ cnt;
preDFS(u, -1);
int x = DFS(u, -1);
for (int i = 2; i >= 0; -- i)
{
if (t[i] < x)
{
for (int j = 0; j < i; ++ j)
{
t[j] = t[j + 1];
}
t[i] = x;
break;
}
}
}
}
if (cnt >= 2)
{
res = max(res, t[1] + t[2] + l);
}
if (cnt >= 3)
{
res = max(res, t[0] + t[1] + 2 * l);
}
return res;
}
void read()
{
int n, m, l;
cin >> n >> m >> l;
vector<int> A(m), B(m), T(m);
for (int i = 0; i < m; ++ i)
{
cin >> A[i] >> B[i] >> T[i];
}
cout << travelTime(n, m, l, A, B, T);
}
void solve()
{
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".IN", "r"))
{
freopen(TASK".IN", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case " << __ << ": ";
read();
solve();
}
}
Compilation message
dreaming.cpp: In function 'int main()':
dreaming.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | freopen(TASK".IN", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cchAvHXp.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccn9xsep.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccn9xsep.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
