oj.uz

Submission #698567

# Submission time Handle Problem Language Result Execution time Memory
698567 2023-02-13T20:08:44 Z blue Sightseeing (NOI14_sightseeing) C++17
25 / 25
 3343 ms 262144 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4684 KB Output is correct
2 Correct 26 ms 3804 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3343 ms 181660 KB Output is correct
2 Correct 3256 ms 262144 KB Output is correct