oj.uz

답안 #1114360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114360 2024-11-18T16:45:18 Z raspy 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
 2 ms 6480 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

#define ll long long
#define inf 1'000'000'000'000
#define f first
#define s second
#define ii pair<ll, ll>

using namespace std;

vector<pair<ll, ll>> graf[100005];
pair<ll, ll> dp[100005];

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
	for (int i = 0; i < m; i++)
	{
		graf[R[i][0]].push_back({R[i][1], L[i]});
		graf[R[i][1]].push_back({R[i][0], L[i]});
	}
	for (int i = 0; i < n; i++)
		dp[i].first = dp[i].second = inf;
	priority_queue<ii> pq;
	for (int i = 0; i < k; i++)
	{
		pq.push({0, P[i]});
		dp[P[i]] = {0, 0};
	}
	while (!pq.empty())
	{
		ii t = pq.top();
		pq.pop();
		if (t.f > dp[t.s].s) continue;
		for (auto [v, w] : graf[t.s])
		{
			if (dp[v].s <= t.f+w) continue;
			if (dp[v].f == inf) dp[v].f = t.f+w;
			else dp[v].s = t.f+w;
			if (dp[v].s != inf)
				pq.push({dp[v].s, v});
		}
	}
	return dp[0].s;
}

// signed main()
// {
// 	return 0;
// }

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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