Submission #700876

#	Time	Username	Problem	Language	Result	Execution time	Memory
700876		Potato3218	Sightseeing (NOI14_sightseeing)	C++17	15 / 25	2561 ms	262144 KiB

sightseeing

#include <bits/stdc++.h>
using namespace std;
#define beegspeed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define pi pair<int,int>

template<typename T>
void print(T t){
	cout<<t;
	exit(0);
}

vector<pi> adjlist[500007];
signed main(){
	beegspeed
	int n, edges, queries; cin>>n>>edges>>queries;
	for(int i = 0; i < edges; i++){
		int origin, dest, weight; cin>>origin>>dest>>weight;
		adjlist[origin].push_back({dest,weight});
		adjlist[dest].push_back({origin,weight});
	}
	priority_queue<pi> pq;
	pq.push({1000000,1});
	int dist[500007];
	memset(dist, -1, sizeof dist);
	dist[1] = 1000000;
	while(!pq.empty()){
		pi edge = pq.top();
		pq.pop();
		if(edge.first != dist[edge.second]) continue;
		for(auto itr: adjlist[edge.second]){
			if(dist[itr.first] == -1 or dist[itr.first] < min(edge.first, itr.second)){
				dist[itr.first] = min(edge.first, itr.second);
				pq.push({dist[itr.first], itr.first});
			}
		}
	}
	for(int i = 0; i < queries; i++){
		int query; cin>>query;
		cout<<dist[query]<<'\n';
	}
}

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