제출 #18258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18258		tlwpdus	Sightseeing (NOI14_sightseeing)	C++98	15 / 25	2571 ms	262144 KiB

sightseeing

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>

using namespace std;

struct edge{
	int i, j, w;
	edge(int i, int j, int w):i(i),j(j),w(w){}
	edge(){}
	inline bool operator < (const edge &A) const {return w<A.w;}
};

vector<edge> lis[500100];
int n, m, q;
int ans[500100];
priority_queue<edge> pq;

const int INF = 1e9;

void prim() {
	int i;
	memset(ans,-1,sizeof(ans));
	ans[0] = INF;
	for (i=0;i<lis[0].size();i++) pq.push(lis[0][i]);
	while(!pq.empty()) {
		edge te = pq.top();
		pq.pop();
		if (ans[te.j]!=-1) continue;
		int here = te.j;
		ans[here] = min(ans[te.i],te.w);
		for (i = 0;i<lis[here].size();i++) pq.push(lis[here][i]);
	}
}

void process() {
	int i;
	prim();
	for (i=0;i<q;i++) {
		int a;
		scanf("%d",&a);
		--a;
		printf("%d\n",ans[a]);
	}
}

void input() {
	int i;
	scanf("%d %d %d",&n,&m,&q);
	for (i=0;i<m;i++) {
		int a, b, w;
		scanf("%d %d %d",&a,&b,&w);
		--a;--b;
		lis[a].push_back(edge(a,b,w));
		lis[b].push_back(edge(b,a,w));
	}
}

int main() {
	input();
	process();
	return 0;
}

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