#include <bits/stdc++.h>
///#include "dreaming.h"
#define MAX 105000
typedef std::pair<int,int> pii;
std::vector<pii> con[MAX];
bool foi[MAX];
int visitou[MAX]={};
int turno=42;
int mais_distante(int x){
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0,x});
int last=0;
++turno;
while(queue.size()){
auto __ = queue.top();
queue.pop();
if(visitou[__.second]==turno)continue;
visitou[__.second]=turno;
last=__.second;
for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
}
return last;
}
int maior_distancia(int x){
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0,x});
int last=0;
++turno;
while(queue.size()){
auto __ = queue.top();
queue.pop();
if(visitou[__.second]==turno)continue;
visitou[__.second]=turno;
last=__.first;
for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
}
return last;
}
std::vector<int> marcar(int x){
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0,x});
std::vector<int> v;
++turno;
while(queue.size()){
auto __ = queue.top();
queue.pop();
if(visitou[__.second]==turno)continue;
visitou[__.second]=turno;
v.push_back(__.second);
foi[__.second]=true;
for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
}
return v;
}
int maiordist[MAX]={};
int meio(int x){
int ponta1 = mais_distante(mais_distante(x));
int ponta2 = mais_distante(ponta1);
std::vector<int> checar;
{
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0,ponta1});
bool visitou[MAX]={};
while(queue.size()){
auto __ = queue.top();
queue.pop();
if(visitou[__.second])continue;
visitou[__.second]=true;
checar.push_back(__.second);
maiordist[__.second]=__.first;
for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
}
}
{
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0,ponta2});
bool visitou[MAX]={};
while(queue.size()){
auto __ = queue.top();
queue.pop();
if(visitou[__.second])continue;
visitou[__.second]=true;
maiordist[__.second]=std::max(maiordist[__.second],__.first);
for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
}
}
int best=-1;
int val=1e9+7;
for(auto&x:checar){
if(maiordist[x]<val){
val=maiordist[x];
best=x;
}
}
return best;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i=0;i!=M;++i){
con[A[i]].push_back({B[i],T[i]});
con[B[i]].push_back({A[i],T[i]});
}
std::vector<std::vector<int>> vec;
for(int i=0;i!=N;++i){
if(foi[i])continue;
vec.push_back(marcar(i));
}
std::vector<int> meios;
for(auto&x:vec){
meios.push_back(meio(x[0]));
}
for(int i=1;i!=meios.size();++i){
con[meios[i]].push_back({meios[0],L});
con[meios[0]].push_back({meios[i],L});
}
return maior_distancia(mais_distante(mais_distante(0)));
}
int main()
{
int a[] = {0,8,2,5,5,1,1,10},b[]={8,2,7,11,1,3,9,6},c[]={4,2,4,3,7,1,5,3};
std::cout<<travelTime(12,8,2,a,b,c)<<"\n";
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i=1;i!=meios.size();++i){
| ~^~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc6Xf8EF.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccQ7SMJF.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccQ7SMJF.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
