Submission #5693

#	Time	Username	Problem	Language	Result	Execution time	Memory
5693		cki86201	Sightseeing (NOI14_sightseeing)	C++98	25 / 25	3312 ms	161732 KiB

sightseeing

#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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10