| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1361650 | midari | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int best_path(int n, int k, int H[][2], int L[]){
vector<int>adj[200100];
int dist[1005][1005];
for (int i=1; i<n; i++){
int u=H[i][0];
int v=H[i][1];
int l=L[i];
adj[u].push_back(v);
adj[v].push_back(u);
dist[u][v]=l;
dist[v][u]=l;
}
int e=intONG_MAX;
int dfh1[200100],dfh2[200100];
for (int i=1; i<=n; i++){
queue<int>q;
q.push(i);
int vis[n+5]={0};
dfh1[i]=0;
dfh2[i]=0;
while (!q.empty()){
int a=q.front();
q.pop();
vis[a]=1;
for (auto u : adj[a]){
if (vis[u]!=1){
vis[u]=1;
q.push(u);
dfh1[u]=dfh1[a]+dist[a][u];
dfh2[u]=dfh2[a]+1;
if (dfh1[u]==k){
e=min(e,dfh2[u]);
}
}
}
}
}
if (e==intONG_MAX){
return -1;
}
else {
return e;
}
}