백준 15591 MooTube (Silver)

백준 15591←클릭

간선의 갯수가 N-1개 이므로 특정 지점에서 출발하였을 경우 다른 노드를 2번 방문할 일은 없다.
고로 단순 BFS로 구현 가능하다.

아이디어

• BFS를 통해 mid를 계속 갱신한다.
• min_dist[start][end] = min(min_dist[start][mid], dist);
  여기서 dist는 mid와 end사이의 거리이다.

코드

github

#define ll long long
#define INF 987654321987654321
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct INFO {
	int to;
	ll dist;
};
int N, Q;
vector<INFO> v[5001];
bool visited[5001][5001];
ll min_dist[5001][5001];
bool print = false;
int main() {
	cin >> N >> Q;
	for (int i = 1; i < N; i++) {
		int from1, to1;
		ll cost;
		cin >> from1 >> to1 >> cost;
		INFO input;
		input.to = to1;
		input.dist = cost;
		v[from1].push_back(input);
		input.to = from1;
		v[to1].push_back(input);
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			min_dist[i][j] = INF;
		}
	}
	while (Q--) {

		int ans = 0;
		int K, start;
		cin >> K >> start;
		for (int i = 1; i <= N; i++)visited[start][i] = false;
		queue<int> q;
		q.push(start);
		while (!q.empty()) {
			int mid = q.front();
			visited[start][mid] = true;

			q.pop();
			for (int i = 0; i < v[mid].size(); i++) {
				int end = v[mid][i].to;
				ll dist = v[mid][i].dist;
				if (visited[start][end] || dist < K) continue;
				q.push(end);
				min_dist[start][end] = min(min_dist[start][mid], dist);
				visited[start][end] = true;
				if (min_dist[start][end] >= K) ans++;
				if (print) printf("min_dist[%d][%d]: %d\n", start, end, min_dist[start][end]);
			}
		}
		cout << ans << endl;
	}
	return 0;
}