제출 #1172696

#제출 시각아이디문제언어결과실행 시간메모리
1172696jadai007악어의 지하 도시 (IOI11_crocodile)C++20
0 / 100
2096 ms320 KiB
#include "crocodile.h" #include <bits/stdc++.h> using namespace std; /*#define MAX_N 50000 #define MAX_M 10000000 static int N, M; static int R[MAX_M][2]; static int L[MAX_M]; static int K; static int P[MAX_N]; static int solution; inline void my_assert(int e) {if (!e) abort();} void read_input() { int i; my_assert(3==scanf("%d %d %d",&N,&M,&K)); for(i=0; i<M; i++) my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i])); for(i=0; i<K; i++) my_assert(1==scanf("%d",&P[i])); my_assert(1==scanf("%d",&solution)); } */ int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){ priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; vector<pair<int, int>> vc[N]; int dis[N][2]; for(int i = 0; i < N; ++i) dis[i][0] = dis[i][1] = 1e9 + 7; for(int i = 0; i < M; ++i) vc[R[i][0]].emplace_back(R[i][1], L[i]), vc[R[i][1]].emplace_back(R[i][0], L[i]); for(int i = 0; i < K; ++i) dis[P[i]][0] = dis[P[i]][1] = 0, pq.emplace(0, P[i]); while(!pq.empty()){ int u = pq.top().second, cnt = pq.top().first; if(dis[u][1] < cnt) continue; for(auto x:vc[u]){ int v = x.first, w = x.second; if(dis[v][0] > w + cnt){ if(dis[v][0] < dis[v][1]) pq.emplace(dis[v][0], v); dis[v][1] = dis[v][0]; dis[v][0] = cnt + w; } else if(dis[v][1] > w + cnt){ dis[v][1] = w + cnt; pq.emplace(dis[v][1], v); } } } return dis[0][1]; } /* int main() { int ans; read_input(); ans = travel_plan(N,M,R,L,K,P); if(ans==solution) printf("Correct.\n"); else printf("Incorrect. Returned %d, Expected %d.\n",ans,solution); return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...