# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
64660 | zetapi | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <crocodile.h>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define itr ::iterator
typedef pair<int,int> pii;
const int MAX=1e6;
const int INF=1e12;
vector<pii> vec[MAX];
int dp[MAX];
void dfs(int node,int par)
{
if(vec[node].size()==1 and vec[node][0].first==par)
return ;
int f=INF,s=INF;
for(auto A:vec[node])
{
if(A.first==par)
continue;
dfs(A.first,node);
if(dp[A.first]+A.second<s)
s=dp[A.first]+A.second;
if(f>s)
swap(f,s);
}
dp[node]=s;
return ;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for(int A=0;A<M;A++)
{
vec[R[A][0]].pb(mp(R[A][1],L[A]));
vec[R[A][1]].pb(mp(R[A][0],L[A]));
}
for(int A=0;A<N;A++)
{
if(vec[A].size()>1)
{
dfs(A,-1);
return dp[A];
}
}
}
/*signed main()
{
ios_base::sync_with_stdio(false);
return 0;
}*/