# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
234717 | Dilshod_Imomov | Crocodile's Underground City (IOI11_crocodile) | C++17 | 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"
using namespace std;
const int NN = 1e3 + 7;
vector < pair < int, int > > adj[NN];
int dp[NN], l[NN];
void dfs( int v, int p ) {
int mn1 = 0, mn2 = 0;
// cout << v << ' ' << p << '\n';
for ( auto pr: adj[v] ) {
int u = pr.first, ind = pr.second;
if ( u != p ) {
dfs( u, v );
int cnt = dp[u] + l[ind];
if ( cnt <= mn1 ) {
mn2 = mn1;
mn1 = cnt;
}
else if ( cnt < mn2 ) {
mn2 = cnt;
}
}
}
if ( mn2 == 0 ) {
mn2 = mn1;
}
dp[v] = mn2;
}
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
for ( int i = 0; i < m; i++ ) {
int u = R[i][0], v = R[i][1];
adj[u].push_back( { v, i } );
adj[v].push_back( { u, i } );
l[i] = L[i];
}
dfs( 0, 0 );
return dp[0];
}