#include "dreaming.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
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]);
if(roots.size() >= 2) res = max(res, L - roots[0] - roots[1]);
int res0 = res;
if(roots.size() >= 3) res0 = max(res0, 2*L - roots[1] - roots[2]);
int res1 = res;
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:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i = 0; i < edge[u].size(); i++)
| ~~^~~~~~~~~~~~~~~~
dreaming.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int i = 0; i < edge[r].size(); i++)
| ~~^~~~~~~~~~~~~~~~
dreaming.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0; i < roots.size(); i++) roots[i] = -1 * maxdist[roots[i]];
| ~~^~~~~~~~~~~~~~
dreaming.cpp:111:16: error: 'res2' was not declared in this scope; did you mean 'res1'?
111 | res = min(res, res2);
| ^~~~
| res1
