답안 #302668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
302668	2020-09-19T03:16:18 Z	shrek12357	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	678 ms	54636 KB

crocodile

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include "crocodile.h"
using namespace std;

const long long INF = 1e10;
const int MAXN = 1e5+5;
#define ll long long

priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pair<ll , ll> dist[MAXN];
bool vis[MAXN];
vector<pair<int, int>> adjList[MAXN];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	for (int i = 0; i < m; i++) {
		adjList[r[i][0]].push_back({ r[i][1], l[i] });
		adjList[r[i][1]].push_back({ r[i][0], l[i] });
	}
	for (int i = 0; i < n; i++) {
		dist[i] = { INF, INF };
		vis[i] = false;
	}
	for (int i = 0; i < k; i++) {
		dist[p[i]] = { 0, 0 };
		pq.push({ 0, p[i] });
	}
	while (pq.size() > 0) {
		int cur = pq.top().second;
		int d = pq.top().first;
		pq.pop();
		if (vis[cur] || d != dist[cur].second) {
			continue;
		}
		if (cur == 0) {
			return d;
		}
		vis[cur] = true;
		for (auto i : adjList[cur]) {
			if (vis[i.first]) {
				continue;
			}
			if (d + i.second > dist[i.first].second) {
				continue;
			}
			if (d + i.second < dist[i.first].first) {
				dist[i.first].second = dist[i.first].first;
				dist[i.first].first = d + i.second;
			}
			else {
				dist[i.first].second = d + i.second;
			}
			pq.push({ d + i.second, i.first });
		}
	}
}

Compilation message

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

Subtask #1

46.0 / 46.0

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

Subtask #2

43.0 / 43.0

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

Subtask #3

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2688 KB	Output is correct
2	Correct	2 ms	2688 KB	Output is correct
3	Correct	2 ms	2688 KB	Output is correct
4	Correct	3 ms	2816 KB	Output is correct
5	Correct	3 ms	2816 KB	Output is correct
6	Correct	3 ms	2816 KB	Output is correct
7	Correct	3 ms	2816 KB	Output is correct
8	Correct	3 ms	2816 KB	Output is correct
9	Correct	4 ms	2944 KB	Output is correct
10	Correct	2 ms	2688 KB	Output is correct
11	Correct	3 ms	2816 KB	Output is correct
12	Correct	7 ms	3200 KB	Output is correct
13	Correct	6 ms	3200 KB	Output is correct
14	Correct	2 ms	2688 KB	Output is correct
15	Correct	3 ms	2816 KB	Output is correct
16	Correct	570 ms	51124 KB	Output is correct
17	Correct	99 ms	14584 KB	Output is correct
18	Correct	115 ms	16120 KB	Output is correct
19	Correct	678 ms	54636 KB	Output is correct
20	Correct	351 ms	43384 KB	Output is correct
21	Correct	48 ms	7928 KB	Output is correct
22	Correct	396 ms	38800 KB	Output is correct