# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
934399 | 2024-02-27T09:39:26 Z | bmh123456789asdf | Crocodile's Underground City (IOI11_crocodile) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h> #define int long long using namespace std; const int N = 2e6 + 1; int par[N]; vector<pair<int,int>> adj[N]; set<int> chamber; int Exit[N], dp[N]; int n, m, k; void dfs(int u,int par) { set<int> ans; dp[u] = 0; if(chamber.find(u) != chamber.end()) Exit[u] = 1; else{ for(auto v : adj[u]) { if(v.first == par) continue; dfs(v.first, u); Exit[u] = max(Exit[u], Exit[v.first]); if(Exit[v.first]) ans.insert(dp[v.first] + v.second); } auto itr = ans.begin(); itr++; dp[u] = *itr; } } int32_t main() { // freopen("test.inp", "r" ,stdin); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> k; for(int i = 1; i <= m; i++) { int u, v, l; cin >> u >> v >> l; adj[u].push_back({v, l}); adj[v].push_back({u, l}); } for(int i = 1; i <= k; i++) { int u; cin >> u; chamber.insert(u); } dfs(0, -1); cout<<dp[0]; }