답안 #872126

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872126 2023-11-12T10:49:47 Z dsyz 악어의 지하 도시 (IOI11_crocodile) C++17
100 / 100
524 ms 104888 KB
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
using ll = long long;
#define MAXN (100005)
vector<pair<ll,ll> > v[MAXN];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
ll secondbest[MAXN]; //second best distance
ll visited[MAXN]; //number of times node i is visited
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for(ll i = 0;i < M;i++){
		ll a = R[i][0];
		ll b = R[i][1];
		ll c = L[i];
		v[a].push_back({c,b});
		v[b].push_back({c,a});
	}
	memset(secondbest,-1,sizeof(secondbest));
	for(ll i = 0;i < K;i++){
		pq.push({0,P[i]});
		visited[P[i]] = 2; //we only need to visit exit nodes once anyways so just set it to 2
	}
	while(!pq.empty()){
		ll d = pq.top().first;
		ll x = pq.top().second;
		pq.pop();
		visited[x]++;
		if(visited[x] >= 2){ //if visited at least twice, we can choose the second best distance among all the distances
			if(secondbest[x] != -1 && d >= secondbest[x]) continue; //worse than pre-existing second best distance so far
			if(secondbest[x] == -1){
				secondbest[x] = d;
			}else{
				secondbest[x] = min(secondbest[x],d);
			}
		}else{
			continue;
		}
		for(auto u : v[x]){
			if(secondbest[u.second] == -1 || secondbest[x] + u.first < secondbest[u.second]){
				pq.push({secondbest[x] + u.first,u.second});
			}
		}
	}
	return secondbest[0];
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 5 ms 9564 KB Output is correct
13 Correct 5 ms 9564 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 5 ms 9564 KB Output is correct
13 Correct 5 ms 9564 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct
16 Correct 496 ms 103328 KB Output is correct
17 Correct 55 ms 21844 KB Output is correct
18 Correct 75 ms 24160 KB Output is correct
19 Correct 524 ms 104888 KB Output is correct
20 Correct 381 ms 90380 KB Output is correct
21 Correct 31 ms 16220 KB Output is correct
22 Correct 331 ms 69832 KB Output is correct