제출 #531004

#제출 시각아이디문제언어결과실행 시간메모리
531004mat50013악어의 지하 도시 (IOI11_crocodile)C++11
100 / 100
506 ms51912 KiB
#include "crocodile.h" #include <bits/stdc++.h> using namespace std; using ll = long long; const int MAX_N(100005); vector<pair<int, int> > G[MAX_N + 5]; ll distF[MAX_N + 5], distS[MAX_N + 5]; bool viz[MAX_N + 5]; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { for(int i = 0; i < M; ++i) G[R[i][0]].push_back({R[i][1], L[i]}), G[R[i][1]].push_back({R[i][0], L[i]}); for(int i = 0; i < N; ++i) distF[i] = 1e9 + 5, distS[i] = 1e9 + 5; priority_queue<pair<ll, int>, vector<pair<ll, int> > , greater<pair<ll, int> > > q; for(int i = 0; i < K; ++i) { distF[P[i]] = distS[P[i]] = 0; q.push({0, P[i]}); } while(!q.empty()) { int nd = q.top().second; ll dist = q.top().first; q.pop(); if(distS[nd] < dist || viz[nd]) continue; viz[nd] = 1; for(auto it: G[nd]) if(distF[it.first] == 1e9 + 5) { distF[it.first] = dist + it.second; q.push({distS[it.first], it.first}); } else if(distS[it.first] == 1e9 + 5 || dist + it.second < distS[it.first]){ distS[it.first] = dist + it.second; if(distF[it.first] > distS[it.first]) swap(distF[it.first], distS[it.first]); q.push({distS[it.first], it.first}); } } return distS[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...