제출 #1195644

#제출 시각아이디문제언어결과실행 시간메모리
1195644pete555Crocodile's Underground City (IOI11_crocodile)C++20
100 / 100
276 ms46904 KiB
#include<bits/stdc++.h> using namespace std; #define pi pair<int,int> #define ll long long #define pb push_back #define pf push_front // void fileIO(string filename) { // freopen((filename + ".in").c_str(), "r", stdin); // freopen((filename + ".out").c_str(), "w", stdout); // } int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){ vector<pi> adj[N]; 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]}); } vector<vector<int>> d(N, vector<int>(2, 1e9)); priority_queue<pi> pq; for(int i = 0; i < K; i++){ pq.push({0, P[i]}); d[P[i]][0] = d[P[i]][1] = 0; } while(pq.size()){ auto [cdist, u] = pq.top(); pq.pop(); cdist *= -1; if(cdist > d[u][1]) continue; for(const auto [v, w] : adj[u]){ int new_len = cdist + w; if(new_len < d[v][0]){ if(d[v][0] < d[v][1]) pq.push({-d[v][0], v}); d[v][1] = d[v][0]; d[v][0] = new_len; } else if(new_len < d[v][1]){ d[v][1] = new_len; pq.push({-d[v][1], v}); } } } return d[0][1]; } // int main() // { // cin.tie(0)->sync_with_stdio(false); // //fileIO(""); // int N, M, K; // cin >> N >> M >> K; // int R[M][2], L[M], P[K]; // for(int i = 0; i < M; i++){ // cin >> R[i][0] >> R[i][1] >> L[i]; // } // for(int i = 0; i < K; i++) cin >> P[i]; // cout << travel_plan(N, M, R, L, K, P); // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...