제출 #1114360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114360		raspy	악어의 지하 도시 (IOI11_crocodile)	C++17	0 / 100	2 ms	6480 KiB

crocodile

#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
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11