| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1315685 | jump | 꿈 (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "dreaming.h"
#define Big_INT long long
Big_INT maxdist1[100010];
Big_INT maxdist2[100010];
Big_INT maxdist3[100010];
std::vector<std::vector<std::pair<Big_INT,Big_INT>>> adj;
std::vector<Big_INT> currentNum;
void bfs(Big_INT start){
std::queue<std::pair<Big_INT,Big_INT>> q;
q.push({start,0});
maxdist1[start]=0;
while(!q.empty()){
Big_INT curr = q.front().first;
currentNum.push_back(curr);
Big_INT currw = q.front().second;
q.pop();
for(auto [to,w]:adj[curr]){
if(maxdist1[to]==-1){
maxdist1[to]=currw+w;
q.push({to,currw+w});
}
}
}
}
void bfs2(Big_INT start){
std::queue<std::pair<Big_INT,Big_INT>> q;
q.push({start,0});
maxdist2[start]=0;
while(!q.empty()){
Big_INT curr = q.front().first;
//currentNum.push_back(curr);
Big_INT currw = q.front().second;
q.pop();
for(auto [to,w]:adj[curr]){
if(maxdist2[to]==-1){
maxdist2[to]=currw+w;
q.push({to,currw+w});
}
}
}
}
void bfs3(Big_INT start){
std::queue<std::pair<Big_INT,Big_INT>> q;
q.push({start,0});
maxdist3[start]=0;
while(!q.empty()){
Big_INT curr = q.front().first;
//currentNum.push_back(curr);
Big_INT currw = q.front().second;
q.pop();
for(auto [to,w]:adj[curr]){
if(maxdist3[to]==-1){
maxdist3[to]=currw+w;
q.push({to,currw+w});
}
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.resize(N+5);
for(Big_INT i=0;i<M;i++){
adj[A[i]].push_back({B[i],T[i]});
adj[B[i]].push_back({A[i],T[i]});
}
for(Big_INT i=0;i<N;i++){
maxdist1[i]=-1;
maxdist2[i]=-1;
maxdist3[i]=-1;
}
std::vector<Big_INT> value;
int maxincomvalue=0;
for(Big_INT i=0;i<N;i++){
if(maxdist1[i]==-1){
bfs(i);
Big_INT nodeA=i,distA=0;
for(auto vNode:currentNum){
if(maxdist1[vNode]>distA){
nodeA=vNode;
distA=maxdist1[vNode];
}
}
bfs2(nodeA);
Big_INT nodeB=nodeA,distB=0;
for(auto vNode:currentNum){
if(maxdist2[vNode]>distB){
nodeB=vNode;
distB=maxdist2[vNode];
}
}
bfs3(nodeB);
Big_INT minmax=1e18;
Big_INT nnn=1e18;
for(auto vNode:currentNum){
minmax=std::min(minmax,std::max(maxdist2[vNode],maxdist3[vNode]));
nnn=std::min(minmax,(maxdist2[vNode]+maxdist3[vNode]));
}
maxincomvalue=std::max(maxincomvalue,nnn);
currentNum.resize(0);
value.push_back(minmax);
}
}
std::sort(value.begin(),value.end());
Big_INT max=value.back();
if(value.size()>=2)max+=value[value.size()-2]+L;
if(value.size()>=3)max=std::max(max,value[value.size()-2]+value[value.size()-3]+2*L);
max=std::max(maxincomvalue,max);
// if(value.size()>=2){
// max=std::max(max,);
// }
return max;
}
int main()
{
int n,m,l;
std::cin >> n >> m >> l;
int a[m],b[m],t[m];
for(int i = 0;i < m;i++) std::cin >> a[i] >> b[i] >> t[i];
std::cout << travelTime(n,m,l,a,b,t);
}