oj.uz

Submission #5692

# Submission time Handle Problem Language Result Execution time Memory
5692 2014-05-13T10:08:43 Z cki86201 Sightseeing (NOI14_sightseeing) C++
15 / 25
 3500 ms 161732 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;

#define X first
#define Y second
typedef pair<int,int> Pi;

int V, E, q;
int st[500050], en[10000010], len[10000010], nxt[10000010];
inline void addE(int s,int e,int c,int l){nxt[c]=st[s],st[s]=c,en[c]=e,len[c]=l;}
int ans[500050];
bool chk[500050];
Pi heap[5000050];

int main()
{
	scanf("%d%d%d",&V,&E,&q);
	int i;
	for(i=1;i<=E;i++){
		int x, y, l;
		scanf("%d%d%d",&x,&y,&l);
		addE(x, y, i<<1, l);
		addE(y, x, i<<1|1, l);
	}
	int top = 1;
	heap[0] = Pi(1e9,1);
	while(top){
		Pi t = heap[0];
		pop_heap(heap, heap+top);
		top--;
		if(chk[t.Y])continue;
		chk[t.Y] = 1;
		ans[t.Y] = t.X;
		for(i=st[t.Y];i;i=nxt[i]){
			if(chk[en[i]])continue;
			heap[top++] = Pi(min(t.X, len[i]), en[i]);
			push_heap(heap, heap+top);
		}
	}
	while(q--){
		int x;
		scanf("%d",&x);
		printf("%d\n",ans[x]);
	}
	return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 161732 KB Output is correct
2 Correct 8 ms 161732 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 161732 KB Output is correct
2 Correct 36 ms 161732 KB Output is correct

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3356 ms 161732 KB Output is correct
2 Execution timed out 3500 ms 161728 KB Program timed out