//#include"dreaming.h"
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int u, w;
};
struct tpos
{
int nodo, dist, padre;
};
int maxn;
const int MAXN = 2e5 + 4;
int Visi[MAXN];
vector<vector<edge>> adj;
struct Component
{
int first;
int second;
};
bool operator < (const Component& a, const Component& b) { return a.second < b.second; }
Component bfs (int nodo)
{
Component ret;
ret.second = -1;
queue<tpos> q;
q.push({nodo, 0, -1});
tpos temp_tpos;
vector<bool> visi(maxn);
while (!q.empty())
{
temp_tpos = q.front(); q.pop();
visi[temp_tpos.nodo] = 1;
Visi[temp_tpos.nodo] = 1;
//cout << " " << temp_tpos.nodo << " " << temp_tpos.dist << "\n";
for (edge e: adj[temp_tpos.nodo])
{
// cout << temp_tpos.nodo << " vecinos: " << e.u << '\n';
if (visi[e.u]) continue;
q.push({e.u, temp_tpos.dist+e.w, temp_tpos.nodo});
}
if (temp_tpos.dist > ret.second)
{
ret.second = temp_tpos.dist;
ret.first = temp_tpos.nodo;
}
}
//cout << '\n';
return ret;
}
tpos Diametro (int pos)
{
int ve = bfs(pos).first;
tpos ttpos;
ttpos.nodo = ve;
Component par = bfs(ve);
ttpos.dist = par.first;
ttpos.padre = par.second;
return ttpos;
}
void DFS(int nodo, int dist, map<int, bool> &visit, map<int, int> &ret)
{
visit[nodo] = 1;
ret[nodo] = dist;
for (edge &e: adj[nodo])
if (visit[e.u]) continue;
else DFS(e.u, dist + e.w, visit, ret);
}
int distanciaxdd (int nodo, map<int, bool> &visit, map<int, int> &a, map<int, int> &b)
{
visit[nodo] = 1;
int mini = max(a[nodo], b[nodo]);
for (edge &e: adj[nodo])
if (visit[e.u]) continue;
else mini = min (mini, distanciaxdd(e.u, visit, a, b));
return mini;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
maxn = N;
adj.resize(N);
edge temp_edge;
for (int i = 0; i < M; i++)
{
temp_edge.u = B[i];
temp_edge.w = T[i];
adj[A[i]].push_back(temp_edge);
temp_edge.u = A[i];
adj[B[i]].push_back(temp_edge);
}
priority_queue<Component> pq;
Component par;
for (int i = 0; i < N; i++)
{
if (Visi[i]) continue;
tpos ttpos = Diametro(i);
par.first = ttpos.padre;
map<int, int> uno, dos;
map<int, bool> visit;
DFS(ttpos.nodo, 0, visit, uno);
visit.clear();
DFS(ttpos.dist, 0, visit, dos);
visit.clear();
par.second = distanciaxdd(i, visit, uno, dos);
// cout << i << " " << par.first << " " << par.second << '\n';
pq.push(par);
}
while (pq.size() > 1)
{
Component a1 = pq.top(); pq.pop();
Component a2 = pq.top(); pq.pop();
// cout << a1.first << ' ' << a2.first << '\n';
Component temporal;
temporal.first = max(a1.first, max(a2.first, a1.second + a2.second + L));
temporal.second = min (max (a1.second + L, a2.second), max(a2.second + L, a1.second));
pq.push(temporal);
}
return pq.top().first;
return 1;
}
int main ()
{
int N, M, L; cin >> N >> M >> L;
int A[N], B[N], T[N];
for (int i = 0; i < M; i++)
cin >> A[i] >> B[i] >> T[i];
cout << travelTime(N, M, L, A, B, T) << endl;
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccsD9MMt.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc2Xuhju.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc2Xuhju.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
