Submission #652829

#	Time	Username	Problem	Language	Result	Execution time	Memory
652829		red24	Sightseeing (NOI14_sightseeing)	C++14	25 / 25	3056 ms	166128 KiB

sightseeing

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define mp make_pair
#define vi vector<int>
#define pi pair<int ,int>
#define vpi vector<pair<int, int>>
#define vvi vector<vector<int>>
#define pqd priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
const int mod = 1e9+7;
#define ll long long

//PROGRAM

int main(){
	// fastio
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// fastio
	
	int n, e, q; cin >> n >> e >> q;
	vpi a[n+1];
	for (int i = 1; i <= e; i++)
	{
		int x, y, c; cin >> x >> y >> c;
		a[x].pb({y, c});
		a[y].pb({x, c});
	}

	priority_queue<pi, vpi> pq;
	vi d(n+1, -1);
	vi vis(n+1);
	
	int s = 1; // 1 is the source
	
	pq.push(mp(0, s));	// push source in the queue
	d[1] = 0;
	while(!pq.empty())
	{
		pi c = pq.top(); pq.pop();
		if (vis[c.second]) continue;
		vis[c.second] = true;
		for (auto x : a[c.second])
		{
			if (vis[x.first]) continue;
			if (c.second == 1)
			{
				d[x.first] = x.second;
				pq.push({x.second, x.first});
				continue;
			}
			if (min(c.first, x.second) > d[x.first])
			{
				d[x.first] = min(c.first, x.second);
				pq.push({d[x.first], x.first});
			}
		}
	}
	
	while(q--)
	{
		int x; cin >> x;
		cout << d[x] << '\n';
	}
}

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