제출 #5267

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

sightseeing

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int E_ = 5000005;
const int V_ = 500005;

int V, E, Q;

struct edge {
	int v, c;
	edge (int v = 0, int c = 0): v(v), c(c) { }
	bool operator< (const edge &e) const { return c > e.c; }
	bool operator> (const edge &e) const { return c < e.c; }
};

vector<edge> Gph[E_];
priority_queue<edge, vector<edge>, greater<edge> > PQ;
int group[V_];
int Res[V_];

int get_group (int u) {
	return (u == group[u]) ? u : (group[u] = get_group(group[u]));
}

const int INF = 250005;
bool visited[V_];

int main() {

	int i, j, k;

	scanf("%d%d%d", &V, &E, &Q);
	for(int i = 1; i <= E; i++) {
		int u, v, c; scanf("%d%d%d", &u, &v, &c);
		Gph[u].push_back (edge(v, c));
		Gph[v].push_back (edge(u, c));
	}

	PQ.push(edge(1, 200005));
	for(int i = 2; i <= V; i++) Res[i] = -1;

	while(!PQ.empty()) {
		edge s = PQ.top(); PQ.pop();
		if(visited[s.v]) continue;
		visited[s.v] = true;
		for(int j = 0; j < Gph[s.v].size(); j++) {
			edge &e = Gph[s.v][j];
			int c = min(e.c, s.c);
			if(c > Res[e.v]) Res[e.v] = c, PQ.push(edge(e.v, c));
		}
	}

	for(int i = 1; i <= Q; i++) {
		int x; scanf("%d", &x);
		printf("%d\n", Res[x]);
	}

	return 0;
}

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