//#include "dreaming.h"
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#define ll long long
#define pii pair <ll, int>
using namespace std;
//int travelTime(int N, int M, int L, int A[], int B[], int T[])
int A[100000], B[100000], T[100000];
map <int, vector <pii>> adj;
map <int, vector <int>> cc;
map <pii, int> edges;
map <int, int> ccnum;
int maxgrp;
ll maxlen = 0;
ll m1 = -1, m2 = -1, m3 = -1;
int main()
{
int N, M, L;
cin >> N >> M >> L;
for (int i = 0; i < M; i++)
{
cin >> A[i] >> B[i] >> T[i];
adj[A[i]].push_back(make_pair(B[i], T[i]));
adj[B[i]].push_back(make_pair(A[i], T[i]));
edges[make_pair(A[i], B[i])] = T[i];
edges[make_pair(B[i], A[i])] = T[i];
}
int cur = 0;
for (int i = 0; i < N; i++)
{
ccnum[i] = -1;
}
for (int i = 0; i < N; i++)
{
if (ccnum[i] == -1)
{
queue <int> curs;
curs.push(i);
ccnum[i] = cur;
while (!curs.empty())
{
int a = curs.front();
curs.pop();
for (auto x : adj[a])
{
if (ccnum[x.first] == -1)
{
ccnum[x.first] = cur;
curs.push(x.first);
}
}
}
cur++;
}
}
for (int i = 0; i < N; i++)
{
cc[ccnum[i]].push_back(i);
}
maxgrp = cur - 1;
for (int i = 0; i <= maxgrp; i++)
{
if (cc[i].size() == 1)
{
if (m3 < 0)
{
m3 = 0;
if (m3 > m2)
{
swap(m3, m2);
if (m2 > m1)
{
swap(m2, m1);
}
}
}
continue;
}
map <int, ll> mins;
for (int a : cc[i])
{
mins[a] = -1;
}
mins[cc[i][0]] = 0;
queue <int> curs;
curs.push(cc[i][0]);
while (!curs.empty())
{
int a = curs.front();
curs.pop();
for (auto b : adj[a])
{
if (mins[b.first] == -1)
{
curs.push(b.first);
mins[b.first] = mins[a] + edges[make_pair(a, b.first)];
}
}
}
int maxl = 0;
int far = 0;
for (int a : cc[i])
{
if (mins[a] > maxl)
{
maxl = mins[a];
far = a;
}
}
map <int, int> parent;
for (int a : cc[i])
{
mins[a] = -1;
}
mins[far] = 0;
curs.push(far);
while (!curs.empty())
{
int a = curs.front();
curs.pop();
for (auto b : adj[a])
{
if (mins[b.first] == -1)
{
curs.push(b.first);
mins[b.first] = mins[a] + edges[make_pair(a, b.first)];
parent[b.first] = a;
}
}
}
maxl = 0;
int far2 = 0;
for (int a : cc[i])
{
if (mins[a] > maxl)
{
maxl = mins[a];
far2 = a;
}
}
int start = far;
int end = far2;
ll length = mins[far2];
ll tot = 0;
if (length > maxlen)
{
maxlen = length;
}
int curpos = far2;
int minmax = 0;
while (tot * 2 < length)
{
tot += edges[make_pair(curpos, parent[curpos])];
if (tot * 2 == length)
{
minmax = tot;
}
if (tot * 2 > length)
{
if (tot * 2 - edges[make_pair(curpos, parent[curpos])] >= length)
{
minmax = length - tot + edges[make_pair(curpos, parent[curpos])];
}
else
{
minmax = tot;
}
}
curpos = parent[curpos];
}
if (m3 < minmax)
{
m3 = minmax;
if (m3 > m2)
{
swap(m3, m2);
if (m2 > m1)
{
swap(m2, m1);
}
}
}
}
if (m2 == -1)
{
return max(maxlen, m1);
}
else if (m3 == -1)
{
return max(maxlen, m1 + L + m2);
}
else
{
return max(maxlen, max(m1 + L + m2, m2 + m3 + 2 * L));
}
}
Compilation message
dreaming.cpp: In function 'int main()':
dreaming.cpp:147:7: warning: unused variable 'start' [-Wunused-variable]
147 | int start = far;
| ^~~~~
dreaming.cpp:148:7: warning: unused variable 'end' [-Wunused-variable]
148 | int end = far2;
| ^~~
/usr/bin/ld: /tmp/ccqxuABV.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccpAFuUX.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccpAFuUX.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
