oj.uz

답안 #583537

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
583537 2022-06-25T14:19:26 Z benson1029 악어의 지하 도시 (IOI11_crocodile) C++14
46 / 100
 3 ms 2932 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;

vector< pair<int,int> > edg[100005];
long long dis[100005], dis1[100005], dis2[100005];
priority_queue< pair<long long, int> > pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for(int i=0; i<N; i++) {
		dis1[i] = dis2[i] = 1e17;
		dis[i] = 2e17;
	}
	for(int i=0; i<M; i++) {
		edg[R[i][0]].push_back({R[i][1], L[i]});
		edg[R[i][1]].push_back({R[i][0], L[i]});
	}
	for(int i=0; i<K; i++) {
		dis[P[i]] = 0;
		pq.push({0, P[i]});
	}
	while(!pq.empty()) {
		int curr = pq.top().second;
		if(dis[curr] != -pq.top().first) {
			pq.pop();
			continue;
		}
		if(curr==0) return dis[curr];
		pq.pop();
		for(auto i:edg[curr]) {
			if(dis[curr]+i.second < dis1[i.first]) {
				dis2[i.first] = dis1[i.first];
				dis1[i.first] = dis[curr]+i.second;
			} else if(dis[curr]+i.second < dis2[i.first]) {
				dis2[i.first] = dis[curr]+i.second;
			} else continue;
			if(dis2[i.first] < 1e17) {
				dis[i.first] = dis2[i.first];
				pq.push({-dis[i.first], i.first});
			}
		}
	}
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
   43 | }
      | ^

Subtask #1
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Incorrect 3 ms 2932 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Incorrect 3 ms 2932 KB Output isn't correct
10 Halted 0 ms 0 KB -