oj.uz

Submission #18258

# Submission time Handle Problem Language Result Execution time Memory
18258 2016-01-26T02:44:58 Z tlwpdus Sightseeing (NOI14_sightseeing) C++
15 / 25
 2571 ms 262144 KB 
#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.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15596 KB Output is correct
2 Correct 2 ms 15256 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17924 KB Output is correct
2 Correct 42 ms 17192 KB Output is correct

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 2571 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -