제출 #1120543

#제출 시각아이디문제언어결과실행 시간메모리
1120543dosts악어의 지하 도시 (IOI11_crocodile)C++17
89 / 100
485 ms93248 KiB
#include "crocodile.h" #include <bits/stdc++.h> using namespace std; #define int long long #define vi vector<int> #define pii pair<int,int> #define ff first #define ss second const int inf = 2e18; int32_t travel_plan(int32_t N, int32_t M, int32_t R[][2], int32_t L[], int32_t K, int32_t P[]) { vector<pii> edges[N]; for (int i=0;i<M;i++) { edges[R[i][0]].push_back({R[i][1],L[i]}); edges[R[i][1]].push_back({R[i][0],L[i]}); } vector<pii> dist(N,pii{inf,inf}); priority_queue<pii,vector<pii>,greater<pii>> pq; for (int i = 0;i<K;i++) { dist[P[i]] = {0,0}; pq.push({0,P[i]}); } while (!pq.empty()) { pii f = pq.top(); pq.pop(); if (dist[f.ss].ss < f.ff) continue; if (f.ff >= inf) continue; for (auto it : edges[f.ss]) { if (f.ff+it.ss < dist[it.ff].ff) { swap(dist[it.ff].ff,dist[it.ff].ss); dist[it.ff].ff = f.ff+it.ss; pq.push({dist[it.ff].ss,it.ff}); } else if (f.ff+it.ss < dist[it.ff].ss) { dist[it.ff].ss = f.ff+it.ss; pq.push({dist[it.ff].ss,it.ff}); } } } if (dist[0].ss >= inf) return -1; return dist[0].ss; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...