//#include "dreaming.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
/*
0 --(1)-- 1
|
(4)
|
4 --(3)-- 5
|
(4)
|
2 --(2)-- 3
Let the root of a connected component be the vertex whose maximum distance from any other vertex in the
connected component is minimum.
All additional edges must be built with both endpoints as roots.
Only one root has more than one additional edge - that with the highest
*/
//complete redo
vector<int> edge[100001];
vector<int> weight[100001];
vector<int> edge_size(1e5 + 1, 0);
vector<int> maxdist(1e5 + 1, 0);
vector<int> visit(1e5 + 1, 0);
vector<int> roots;
struct distcomp
{
int i;
};
bool operator < (distcomp A, distcomp B)
{
if(maxdist[A.i] == maxdist[B.i]) return A.i < B.i;
return maxdist[A.i] < maxdist[B.i];
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for(int i = 0; i < M; i++)
{
edge[A[i]].push_back(B[i]);
weight[A[i]].push_back(T[i]);
edge_size[A[i]]++;
edge[B[i]].push_back(A[i]);
weight[B[i]].push_back(T[i]);
edge_size[B[i]]++;
}
set<distcomp> tbv;
for(int i = 0; i < N; i++)
{
if(edge_size[i] == 1) tbv.insert(distcomp{i});
}
int u, v, w;
int flag;
while(!tbv.empty())
{
u = tbv.begin()->i;
tbv.erase(tbv.begin());
visit[u] = 1;
for(int i = 0; i < edge[u].size(); i++)
{
v = edge[u][i];
w = weight[u][i];
if(visit[v]) continue;
edge_size[v]--;
maxdist[v] = max(maxdist[v], maxdist[u] + w);
flag = 0;
if(edge_size[v] == 1)
{
tbv.insert(distcomp{v});
}
}
}
for(int i = 0; i < N; i++) if(edge_size[i] == 0)
{
roots.push_back(i);
}
int res = 0;
int max1, max2;
for(int r: roots)
{
max1 = max2 = 0;
for(int i = 0; i < edge[r].size(); i++)
{
v = edge[r][i];
w = weight[r][i];
if(maxdist[v] + w >= max1)
{
max2 = max1;
max1 = maxdist[v] + w;
}
else if(maxdist[v] + w >= max2) max2 = maxdist[v] + w;
}
res = max(res, max1 + max2);
}
for(int i = 0; i < roots.size(); i++) roots[i] = -1 * maxdist[roots[i]];
sort(roots.begin(), roots.end());
if(roots.size() >= 2) res = max(res, L - roots[0] - roots[1]);
if(roots.size() >= 3) res = max(res, 2*L - roots[1] - roots[2]);
int res0 = res;
if(roots.size() >= 2) res0 = max(res0, L - roots[0] - roots[1]);
if(roots.size() >= 3) res0 = max(res0, 2*L - roots[1] - roots[2]);
int res1 = res;
if(roots.size() >= 2) res1 = max(res1, L - roots[0] - roots[2]);
if(roots.size() >= 3) res1 = max(res1, 2*L - roots[0] - roots[2]);
res = min(res, res1);
res = min(res, res2);
return res;
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i = 0; i < edge[u].size(); i++)
| ~~^~~~~~~~~~~~~~~~
dreaming.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i = 0; i < edge[r].size(); i++)
| ~~^~~~~~~~~~~~~~~~
dreaming.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i = 0; i < roots.size(); i++) roots[i] = -1 * maxdist[roots[i]];
| ~~^~~~~~~~~~~~~~
dreaming.cpp:134:16: error: 'res2' was not declared in this scope; did you mean 'res1'?
134 | res = min(res, res2);
| ^~~~
| res1
