# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
709127 | 2023-03-13T06:35:10 Z | ono_de206 | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#include "crocodile.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define int long long const int inf = 1e18 + 10; const int mxn = 1e5 + 10; int a[mxn], is[mxn], n; vector<pair<int, int>> g[mxn]; map<int, int> mp; int solve(int x) { if(mp.find(x) != mp.end()) return mp[x]; if(is[x]) return 0; vector<int> tmp; int &ret = mp[x]; ret = inf; for(auto [y, t] : g[x]) { tmp.pb(solve(y) + t); } sort(tmp.begin(), tmp.end()); ret = tmp[1]; return ret; } int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { n = N; for(int i = 0; i < M; i++) { int x = R[i][0]; int y = R[i][1]; g[x].pb({y, L[i]}); g[y].pb({x, L[i]}); } for(int i = 0; i < K; i++) { is[P[i]] = 1; } return solve(0); }