Submission #199739

#TimeUsernameProblemLanguageResultExecution timeMemory
199739shahriarkhanCrocodile's Underground City (IOI11_crocodile)C++14
0 / 100
15 ms5240 KiB
#include<bits/stdc++.h> using namespace std ; #define pii pair<int,int> const int mx = 1e5 + 5 , inf = 1e9 + 10 ; vector<pii> adj[mx] ; int dist[mx] , vis[mx] , ans[mx][2] ; int pass(int a , int d) { if(d<=ans[a][0]) { ans[a][1] = ans[a][0] ; ans[a][0] = d ; dist[a] = ans[a][1] ; return 1 ; } if(d<ans[a][1]) { ans[a][1] = d ; dist[a] = d ; return 1 ; } return 0 ; } int travel_plan(int n , int m , int r[][2] , int l[] , int k , int p[]) { for(int i = 0 ; i < m ; ++i) { int a = r[i][0] , b = r[i][1] ; adj[a].push_back({b,l[i]}) ; adj[b].push_back({a,l[i]}) ; } for(int i = 0 ; i < n ; ++i) dist[i] = ans[i][0] = ans[i][1] = inf ; priority_queue<pii,vector<pii>,greater<pii> > pq ; for(int i = 0 ; i < k ; ++i) { pq.push({0,p[i]}) ; dist[p[i]] = ans[p[i]][0] = ans[p[i]][1] = 0 ; } while(!pq.empty()) { pii pr = pq.top() ; pq.pop() ; int to = pr.second ; if(vis[to]) continue ; vis[to] = 1 ; int siz = adj[to].size() ; for(int i = 0 ; i < siz ; ++i) { int a = pr.first , b = pr.second ; int d = dist[to] + b ; if(pass(a,d)) pq.push({d,ans[a][1]}) ; } } return ans[0][1] ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...