oj.uz

답안 #1072765

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1072765 2024-08-24T04:18:58 Z ssitaram 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
 1 ms 2396 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	vector<vector<pair<int, int>>> adj(n);
	for (int i = 0; i < m; ++i) {
		adj[r[i][0]].push_back({r[i][1], l[i]});
		adj[r[i][1]].push_back({r[i][0], l[i]});
	}
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	vector<priority_queue<ll>> best2(n);
	for (int i = 0; i < k; ++i) {
		pq.push({0, p[i]});
		best2[p[i]].push(0);
	}
	while (!pq.empty()) {
		pair<ll, int> state = pq.top();
		pq.pop();
		if (state.first > best2[state.second].top()) continue;
		if (!state.second) {
			return state.first;
		}
		for (pair<int, int>& edge : adj[state.second]) {
			if (best2[edge.first].size() < 2) {
				best2[edge.first].push(state.first + edge.second);
				pq.push({best2[edge.first].top(), edge.first});
			} else if (state.first + edge.second < best2[edge.first].top()) {
				best2[edge.first].pop();
				best2[edge.first].push(state.first + edge.second);
				pq.push({best2[edge.first].top(), edge.first});
			}
		}
	}
	return 0;
}

Subtask #1
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -