#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100000
static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];
# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;
// idenya dfs dua kali
// yang pertama subtree normal, yang kedua dari luar subtree
vector< pair<int, int> > edge[100001];
bool vis[100001];
int ins[100001];
vector<int> pref[100001], suff[100001];
void dfs(int a, int pr) {
vis[a] = 1;
ins[a] = 0;
for(int k=0;k<edge[a].size();k++) {
if(edge[a][k].fi == pr) continue;
dfs(edge[a][k].fi, a);
ins[a] = max(ins[edge[a][k].fi] + edge[a][k].se, ins[a]);
}
}
int cek, ct;
void fn(int a, int pr, int bf) {
// cout<<"a : "<<a<<" "<<bf<<" "<<ins[a]<<endl;
cek = min(cek, max(bf, ins[a]));
ct = max(ct, max(bf, ins[a]));
pref[a].resize(edge[a].size());
suff[a].resize(edge[a].size());
for(int k=0;k<edge[a].size();k++) {
if(edge[a][k].fi == pr) {
if(k == 0) pref[a][k] = 0;
else pref[a][k] = pref[a][k - 1];
} else {
if(k == 0) pref[a][k] = ins[edge[a][k].fi] + edge[a][k].se;
else pref[a][k] = max(pref[a][k-1], ins[edge[a][k].fi] + edge[a][k].se);
}
}
for(int k=edge[a].size() - 1;k>=0;k--) {
if(edge[a][k].fi == pr) {
if(k == edge[a].size() - 1) suff[a][k] = 0;
else suff[a][k] = suff[a][k + 1];
} else {
if(k == edge[a].size() - 1) suff[a][k] = ins[edge[a][k].fi] + edge[a][k].se;
else suff[a][k] = max(suff[a][k+1], ins[edge[a][k].fi] + edge[a][k].se);
}
}
for(int k=0;k<edge[a].size();k++) {
if(edge[a][k].fi == pr) continue;
int mx = 0;
if(k > 0) mx = max(mx, pref[a][k - 1]);
if(k + 1 < edge[a].size()) mx = max(mx, suff[a][k + 1]);
// cout<<"AA : "<<edge[a][k].fi<<" "<<mx<<" "<<edge[a][k].se<<endl;
fn(edge[a][k].fi, a, max(mx, bf) + edge[a][k].se);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int k=0;k<N;k++) {
edge[k].clear();
vis[k] = 0;
}
for(int i=0;i<M;i++) {
edge[A[i]].push_back(make_pair(B[i], T[i]));
edge[B[i]].push_back(make_pair(A[i], T[i]));
}
vector<int> P;
P.clear();
int ans = 0;
for(int i=0;i<N;i++) {
if(!vis[i]) {
cek = 2e9;
ct = 0;
dfs(i, -1);
fn(i, -1, 0);
ans = max(ans, ct);
P.push_back(cek);
// cout<<cek<<endl;
// cout<<ins[i]<<endl;
// cout<<i<<" "<<cek<<endl;
}
}
sort(P.begin(), P.end());
if(P.size() == 1) return max(P[0], ans);
else if(P.size() == 2) return max(P[0] + P[1] + L, ans);
else {
int t1 = P.back() + L + P[P.size() - 2];
int t2 = P[P.size() - 2] + L + L + P[P.size() - 3];
return max(t1, max(t2, ans));
}
}
int main() {
int N, M, L, i;
int res;
scanf("%d%d%d", &N, &M, &L);
for (i = 0; i < M; i++)
scanf("%d%d%d", &A[i], &B[i], &T[i]);
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}
Compilation message
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int k=0;k<edge[a].size();k++) {
| ~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void fn(int, int, int)':
dreaming.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int k=0;k<edge[a].size();k++) {
| ~^~~~~~~~~~~~~~~
dreaming.cpp:51:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | if(k == edge[a].size() - 1) suff[a][k] = 0;
| ~~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:54:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | if(k == edge[a].size() - 1) suff[a][k] = ins[edge[a][k].fi] + edge[a][k].se;
| ~~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:59:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int k=0;k<edge[a].size();k++) {
| ~^~~~~~~~~~~~~~~
dreaming.cpp:64:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | if(k + 1 < edge[a].size()) mx = max(mx, suff[a][k + 1]);
| ~~~~~~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int main()':
dreaming.cpp:109:6: warning: unused variable 'res' [-Wunused-variable]
109 | int res;
| ^~~
dreaming.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | scanf("%d%d%d", &N, &M, &L);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | scanf("%d%d%d", &A[i], &B[i], &T[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccqNHcEr.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccif8SKr.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccif8SKr.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
