# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
169461 | 2019-12-20T13:33:54 Z | Shafin666 | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#include "crocodile.h" #include <bits/stdc++.h> #define pb push_back #define pii pair<ll, ll> #define nyan "(=^・ω・^=)" #define read_input freopen("in.txt","r", stdin) #define print_output freopen("out.txt","w", stdout) typedef long long ll; typedef long double ld; using namespace std; const ll maxn = 2e5+10; ll dist[maxn], visited[maxn]; vector<pii> adj[maxn]; ll travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { for(ll i = 0; i < M; i++) { adj[R[i][0]].pb({R[i][1], L[i]}); adj[R[i][1]].pb({R[i][0], L[i]}); } for(ll i = 0; i < N; i++) dist[i] = 1e16+7; multiset<pii> s; s.insert({0, 0}); dist[0] = 0; while(!s.empty()) { pii p = *s.begin(); s.erase(s.begin()); ll u = p.second; if(visited[u]) continue; visited[u] = 1; ll mndist = 1e16+7, ver = -1; for(auto p : adj[u]) { ll v = p.first, w = p.second; if(dist[u] + w < dist[v]) { if(dist[u] + w < mndist) mndist = dist[u] + w, ver = v; } } for(auto p : adj[u]) { ll v = p.first, w = p.second; if(v == ver) continue; if(dist[u] + w < dist[v]) { dist[v] = dist[u] + w; s.insert({dist[v], v}); } } } ll ret = 1e16+7; for(ll i = 0; i < K; i++) ret = min(ret, dist[P[i]]); return ret; }