# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1137005 | Ciprian | Crocodile's Underground City (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1003;
vector<int>adj[N], fin(N);
void dfs(int x, int p, vector<vector<int>> t){
if(adj[x].size()==1){
return;
}
for(auto e: adj[x]){
if(e==p)continue;
dfs(e,x, t);
}int mn1=1e9, mn2=1e9;
for(auto e: adj[x]){
if(e==p)continue;
mn1=min(mn1, fin[e]+t[x][e]);
}for(auto e: adj[x]){
if(e==p)continue;
if(fin[e]+t[x][e]!=mn1){
mn2=min(mn2, fin[e]+t[x][e]);
}
}fin[x]=mn2;
}int travel_plan(int N,int M,int R[][2],int L[],int K, int P[]){
vector<vector<int>> tm(N, vector<int>(N));
for(int i=0; i<M; i++){
adj[R[i][0]].push_back(R[i][1]);
adj[R[i][1]].push_back(R[i][0]);
tm[R[i][0]][R[i][1]]=L[i];
tm[R[i][1]][R[i][0]]=L[i];
}dfs(0,0,tm);
return fin[0];
}