# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
561314 | 2022-05-12T15:44:11 Z | Quan2003 | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include <iostream> #include<queue> #include<vector> #include<utility> using namespace std; typedef long long ll; const int sz=1e5+1; ll p[sz]; ll dp[sz]; ll d1[sz]; ll d0[sz]; vector<array<ll,2>>adj[sz]; int n,m,k; void dfs(int u,int p){ for (auto e:adj[u]){ int v=e[0]; if (v==p) continue; dfs(v,u); d1[u]=min(d1[u],d1[v]+e[1]); } if (adj[u].size()>1){ for (auto e:adj[u]){ int v=e[0]; if (v==p) continue; dfs(v,u); if (dp[v]+e[1]==d1[u]) continue; dp[u]=min(dp[u],dp[v]+e[1]); } } } int main(){ cin>>n>>m>>k; for (int i=0;i<n;i++){ dp[i]=LLONG_MAX; d1[i]=LLONG_MAX; } for (int i=0;i<m;i++){ int u,v;ll d; cin>>u>>v>>d; adj[u].push_back({v,d}); adj[v].push_back({u,d}); } for (int i=0;i<k;i++){ cin>>p[i]; dp[p[i]]=0; d1[p[i]]=0; } dfs(0,-1); cout <<dp[0]; }