Submission #698567

#	Time	Username	Problem	Language	Result	Execution time	Memory
698567		blue	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	3343 ms	262144 KiB

sightseeing

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int V, E, Q;
	cin >> V >> E >> Q;

	vpii edge[1 + V];

	for(int e = 1; e <= E; e++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		edge[u].push_back({w, v});
		edge[v].push_back({w, u});
	}

	set<pii> tbv;

	vi dp(1 + V, 0);

	dp[1] = 1'000'000'001;


	tbv.insert({dp[1], 1});

	while(!tbv.empty())
	{
		int u = tbv.rbegin()->second;
		tbv.erase(*tbv.rbegin());

		for(pii vp : edge[u])
		{
			int nw = min(vp.first, dp[u]);

			if(nw > dp[vp.second])
			{
				dp[vp.second] = nw;
				tbv.insert({dp[vp.second], vp.second});
			}
		}
	}


	for(int q = 1; q <= Q; q++)
	{
		int X;
		cin >> X;

		cout << dp[X] << '\n';
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10