oj.uz

답안 #302666

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
302666 2020-09-19T03:13:07 Z shrek12357 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 3 ms 2816 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include "crocodile.h"
#include <fstream>
#include <queue>
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;
		}
		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:63:1: warning: control reaches end of non-void function [-Wreturn-type]
   63 | }
      | ^

Subtask #1
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 3 ms 2688 KB Output is correct
4 Incorrect 3 ms 2816 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
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 3 ms 2688 KB Output is correct
4 Incorrect 3 ms 2816 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
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 3 ms 2688 KB Output is correct
4 Incorrect 3 ms 2816 KB Output isn't correct
5 Halted 0 ms 0 KB -