Submission #927250

#TimeUsernameProblemLanguageResultExecution timeMemory
927250hengliaoCrocodile's Underground City (IOI11_crocodile)C++14
100 / 100
671 ms75968 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define F first #define S second #define pll pair<ll, ll> #define vll vector<ll> #define vllll vector<vector<ll, ll>> #define debug(...) cout<<" [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "<<'\n'; typedef long long ll; const int inf=1e9+5; const int mxN=1e5+5; vector<pair<int, int>> adj[mxN]; int dis[mxN]; bool done[mxN]; int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){ memset(done, 0, sizeof(done)); priority_queue<pair<int, int>> pq; for(int i=0;i<n;i++){ dis[i]=inf; } for(int 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(int i=0;i<k;i++){ dis[p[i]]=0; pq.push({0, p[i]}); } while(!pq.empty()){ pair<int, int> cur=pq.top(); pq.pop(); if(dis[cur.S]<inf && cur.F!=0) continue; if(!done[cur.S] && cur.F!=0){ done[cur.S]=1; continue; } dis[cur.S]=min(-cur.F, dis[cur.S]); for(auto it:adj[cur.S]){ pq.push({-(-cur.F+it.S), it.F}); } } return dis[0]; } /*test case */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...