oj.uz

Submission #5693

# Submission time Handle Problem Language Result Execution time Memory
5693 2014-05-13T10:11:06 Z cki86201 Sightseeing (NOI14_sightseeing) C++
25 / 25
 3312 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];

void getInt(int &a){
	a=0;
	char c=getchar();
	while('0'<=c&&c<='9')a=(a<<3)+(a<<1)+c-'0',c=getchar();
}

int main()
{
	getInt(V), getInt(E), getInt(q);
	int i;
	for(i=1;i<=E;i++){
		int x, y, l;
		getInt(x), getInt(y), getInt(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;
		getInt(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 12 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 28 ms 161732 KB Output is correct
2 Correct 24 ms 161732 KB Output is correct

Subtask #4
10.0 / 10.0

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