답안 #756594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756594	2023-06-12T01:05:16 Z	salmon	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	687 ms	59608 KB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	vector<pair<int,int>> adjlst[100100];
	long long int d[100100];
	int visited[100100];
	priority_queue<pair<long long int, int>,vector<pair<long long int, int>>,greater<pair<long long int, int>>> pq;
	
	for(int i = 0; i < M; i++){
		adjlst[R[i][0]].push_back(make_pair(R[i][1],L[i]));
		adjlst[R[i][1]].push_back(make_pair(R[i][0],L[i]));
	}
	
	for(int i = 0 ; i < N; i++){
		d[i] = 1100100100100100100;
		visited[i] = 0;
	}
	
	for(int i = 0; i < K; i++){
		visited[P[i]] = 1;
		pq.push(make_pair(0,P[i]));
	}
	
	while(!pq.empty()){
		long long int de = pq.top().first;
		int i = pq.top().second;
		pq.pop();
		
		if(visited[i] == 1){
			d[i] = de;
			
			for(pair<int,int> ii : adjlst[i]){
				if(visited[ii.first] > 1) continue;
				pq.push(make_pair(de + ii.second, ii.first));
			}
		}
		visited[i]++;
	}
	
	
	
	return d[0];
}

Subtask #1

46.0 / 46.0

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

Subtask #2

43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	3796 KB	Output is correct
2	Correct	2 ms	3796 KB	Output is correct
3	Correct	2 ms	3796 KB	Output is correct
4	Correct	3 ms	3796 KB	Output is correct
5	Correct	3 ms	3924 KB	Output is correct
6	Correct	3 ms	3796 KB	Output is correct
7	Correct	3 ms	3796 KB	Output is correct
8	Correct	4 ms	3796 KB	Output is correct
9	Correct	4 ms	4180 KB	Output is correct
10	Correct	4 ms	3796 KB	Output is correct
11	Correct	3 ms	3924 KB	Output is correct
12	Correct	7 ms	4564 KB	Output is correct
13	Correct	6 ms	4564 KB	Output is correct
14	Correct	3 ms	3796 KB	Output is correct
15	Correct	4 ms	3924 KB	Output is correct

Subtask #3

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	3796 KB	Output is correct
2	Correct	2 ms	3796 KB	Output is correct
3	Correct	2 ms	3796 KB	Output is correct
4	Correct	3 ms	3796 KB	Output is correct
5	Correct	3 ms	3924 KB	Output is correct
6	Correct	3 ms	3796 KB	Output is correct
7	Correct	3 ms	3796 KB	Output is correct
8	Correct	4 ms	3796 KB	Output is correct
9	Correct	4 ms	4180 KB	Output is correct
10	Correct	4 ms	3796 KB	Output is correct
11	Correct	3 ms	3924 KB	Output is correct
12	Correct	7 ms	4564 KB	Output is correct
13	Correct	6 ms	4564 KB	Output is correct
14	Correct	3 ms	3796 KB	Output is correct
15	Correct	4 ms	3924 KB	Output is correct
16	Correct	669 ms	57316 KB	Output is correct
17	Correct	75 ms	10788 KB	Output is correct
18	Correct	89 ms	12180 KB	Output is correct
19	Correct	687 ms	59608 KB	Output is correct
20	Correct	432 ms	54264 KB	Output is correct
21	Correct	37 ms	7076 KB	Output is correct
22	Correct	399 ms	33264 KB	Output is correct