#include "dreaming.h"
#include<vector>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
bool byGreater(long long int a,long long int b)
{
return a>b;
}
struct edge
{
long long int from,to;
long long int w;
};
vector<edge> adjList[100005];
long long int far[100005]; //Stores the minimum longest distance for each tree
long long int color[100005];
long long int d[2][100005];
queue<long long int> Q;
long long int bfs(long long int s,long long int op,long long int c)
{
color[s]=c;
d[op][s]=0;
Q.push(s);
long long int farthest_node;
long long int maximum=0;
while(Q.size()){
long long int u=Q.front();Q.pop();
for(edge e: adjList[u]){
long long int v=e.to;
if(color[v]!=c){
color[v]=c;
d[op][v]=d[op][u]+e.w;
if(d[op][v]>maximum){
maximum=d[op][v];
farthest_node=v;
}
Q.push(v);
}
}
}
return farthest_node;
}
long long int getOptimumDistance(long long int s,long long int c)
{
color[s]=c;
long long int minimumD=1000000000;
Q.push(s);
while(Q.size()){
long long int u=Q.front();Q.pop();
if(max(d[0][u],d[1][u])<minimumD){
minimumD=max(d[0][u],d[1][u]);
}
for(edge e: adjList[u]){
long long int v=e.to;
if(color[v]!=c){
color[v]=c;
Q.push(v);
}
}
}
return minimumD;
}
long long int travelTime(long long int N, long long int M, long long int L, long long int A[], long long int B[], long long int T[]) {
for(long long int i=0;i<M;i++){
edge e={A[i],B[i],T[i]};
adjList[e.from].push_back(e);
swap(e.from,e.to);
adjList[e.from].push_back(e);
}
long long int answer=0;
long long int max_diameter=0;
long long int c=1;
long long int trees=0;
for(long long int u=0;u<N;u++){
if(color[u]!=0) continue;
long long int a=bfs(u,1,c++);
long long int b=bfs(a,0,c++);
bfs(b,1,c++);
max_diameter=max(max_diameter,d[1][a]);
far[trees++]=getOptimumDistance(u,c++);
}
sort(far,far+trees,byGreater);
if(trees==1){
answer=max_diameter;
}
else if(trees==2){
answer=max(max_diameter,far[0]+L+far[1]); //Path joining yourself with another tree
}
else{
answer=max(max_diameter,
max(far[0]+L+far[1],far[1]+L+L+far[2])); //Path joining yourself with another tree
//and joining other two trees whose path passes for you
}
return answer;
}
Compilation message
dreaming.cpp: In function 'long long int bfs(long long int, long long int, long long int)':
dreaming.cpp:43:12: warning: 'farthest_node' may be used uninitialized in this function [-Wmaybe-uninitialized]
return farthest_node;
^~~~~~~~~~~~~
/tmp/ccw77ad2.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
