#include <stdio.h>
#include <vector>
#include "dreaming.h"
#define MAX_N 100001
#define oo (1<<30)
using namespace std;
vector< pair<int,int> > E[MAX_N];
int ebm, ebm2, ebm3, eb, en;
int uzak[MAX_N][2], kul[MAX_N];
int DFS(int dugum, int ata) {
kul[dugum] = 1;
for (int i = 0; i < E[dugum].size(); i++) {
int v = E[dugum][i].first, m = E[dugum][i].second;
if (v != ata) {
int s = DFS(v, dugum) + m;
if(s > uzak[dugum][0]) {
uzak[dugum][1] = uzak[dugum][0];
uzak[dugum][0] = s;
}
else if(s > uzak[dugum][1])
uzak[dugum][1] = s;
}
}
// printf("dugum: %d, ata: %d, uzak0: %d, uzak1: %d\n", dugum, ata,uzak[dugum][0], uzak[dugum][1]);
return uzak[dugum][0];
}
void DFS2(int dugum, int ata, int m) {
//printf("Dugum: %d, ata: %d, m: %d, eb: %d, uzak[dugum][0]: %d\n", dugum, ata, m, eb, uzak[dugum][0]);
if (ata != -1)
if (uzak[ata][0] == uzak[dugum][0] + m) {
if (uzak[dugum][0] < uzak[ata][1] + m) {
uzak[dugum][1] = uzak[dugum][0];
uzak[dugum][0] = uzak[ata][1] + m;
}
else if (uzak[dugum][1] < uzak[ata][1] + m)
uzak[dugum][1] = uzak[ata][1] + m;
}
else {
uzak[dugum][1] = uzak[dugum][0];
uzak[dugum][0] = uzak[ata][0] + m;
uzak[dugum][1] = max(uzak[dugum][1], uzak[ata][1] + m)
}
//printf("Dugum: %d, ata: %d, m: %d, eb: %d, uzak[dugum][0]: %d\n", dugum, ata, m, eb, uzak[dugum][0]);
for (int i = 0; i < E[dugum].size(); i++) {
int v = E[dugum][i].first, mm = E[dugum][i].second;
if (v != ata)
DFS2(v, dugum, mm);
}
// printf("Dugum: %d, ata: %d, m: %d, eb: %d, uzak[dugum][0]: %d\n", dugum, ata, m, eb, uzak[dugum][0]);
eb = min(eb, uzak[dugum][0]);
en = max(en, uzak[dugum][0]);
}
void merkezleriBul(int N) {
for (int i = 0; i < N; i++) {
if (!kul[i]) {
eb = oo;
DFS(i, -1);
DFS2(i, -1, 0);
// printf("%d\n", eb);
if (eb > ebm) {ebm3 = ebm2; ebm2 = ebm; ebm = eb;}
else if (eb > ebm2) {ebm3 = ebm2; ebm2 = eb;}
else if (eb > ebm3) ebm3 = eb;
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++) {
E[ A[i] ].push_back( make_pair(B[i], T[i]) );
E[ B[i] ].push_back( make_pair(A[i], T[i]) );
}
merkezleriBul(N);
int sonuc;
sonuc = max(ebm + ebm2 + L, ebm2 + ebm3 + 2*L);
sonuc = max(sonuc, en);
return sonuc;
}
/*
#include <stdio.h>
#include <stdlib.h>
#include "dreaming.h"
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];
int main() {
int N, M, L, i;
int res;
FILE *f = fopen("sample.in", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d%d%d", &N, &M, &L);
for (i = 0; i < M; i++)
res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
fclose(f);
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}*/
Compilation message
dreaming.cpp: In function 'int DFS(int, int)':
dreaming.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < E[dugum].size(); i++) {
~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void DFS2(int, int, int)':
dreaming.cpp:50:2: error: expected ';' before '}' token
}
^
dreaming.cpp:37:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if (ata != -1)
^
dreaming.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < E[dugum].size(); i++) {
~~^~~~~~~~~~~~~~~~~
