MooTube (Silver) (feat. 백준, 15591번)

MooTube (Silver)
https://www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <set>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, Q;
	set<pair<int, int>> arr[5001];
	bool visit[5001];
	cin >> N >> Q;
	for (register int n = 1, p, q, r; n < N; ++n) {
		cin >> p >> q >> r;
		arr[p].insert(make_pair(q, r)), arr[q].insert(make_pair(p, r));
	}
	register int ans = 0;
	queue<int> q;
	for (register int qq = 0, k, v; qq < Q; ++qq) {
		cin >> k >> v;
		memset(visit, false, N + 1);
		ans = 0;
		q.push(v);
		visit[v] = true;
		while (!q.empty()) {
			register int x = q.front(); q.pop();
			for (auto iter = arr[x].begin(); iter != arr[x].end(); ++iter) {
				register int y = iter->first, u = iter->second;
				if (!visit[y] && u >= k)
					++ans, visit[y] = true, q.push(y);
			}
		}
		cout << ans << "\n";
	}
	return 0;
}
// *&)*@*

1. p와 q는 양방향 정점이고 서로간 간선의 길이는 r 입니다.
2. 하나의 정점 (Vi) 과 간선의 길이 (Ki) 가 주어졌을때, 정점과 연결된 모든 간선 중 문제로 주어진 간선의 길이보다 긴 간선은 총 몇개인지를 묻는 문제입니다.