oj.uz

답안 #5267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5267 2014-03-14T11:51:48 Z tncks0121 관광 (NOI14_sightseeing) C++
15 / 25
 3500 ms 262144 KB 
#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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 122792 KB Output is correct
2 Correct 36 ms 122792 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 122936 KB Output is correct
2 Correct 32 ms 122792 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 124640 KB Output is correct
2 Correct 60 ms 124376 KB Output is correct

Subtask #4
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3068 ms 218856 KB Output is correct
2 Execution timed out 3500 ms 262144 KB Program timed out