[백준] 15591-MooTube (Silver)(C++)

문제링크: https://www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

 

접근방식

 

1. 문제를 이해하는게 힘들었던 문제..;;

3. 결국 탐색을 통해서 동영상마다 유사도를 저장해주고 문제를 해결하면 되는 문제

4. 우선순위 큐를 사용한 탐색을 고안(굳이 우선순위일 필요가 없을 것 같긴하다)

 

문제풀이 

 

1. 우선순위큐를 사용하여 동영상별로 유사도를 도출. dist배열에 저장

 

 

코드를 직접 확인하는게 더 빠를 것 같음

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, q;
int a, b, c;
int k, v;
vector <pair<int, int>> vec[5001];
int dist[5001][5001];

void dijkstra(int num) {
	queue <pair<int,int>> que;
	que.push(make_pair(num,2000000000));
	
	while (!que.empty()) {

		int cur = que.front().first;
		int cost = que.front().second;
		que.pop();

		for (int i = 0; i < vec[cur].size(); i++) {
			
			if (dist[num][vec[cur][i].first] != 2000000000)
				continue;
			if (vec[cur][i].second > cost) {
				dist[num][vec[cur][i].first] = cost;
				que.push(make_pair(vec[cur][i].first, cost));
			}
			else {
				dist[num][vec[cur][i].first] = vec[cur][i].second;
				que.push(make_pair(vec[cur][i].first, vec[cur][i].second));
			}

		}


	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> q;
	for (int i = 0; i < n - 1; i++) {
		cin >> a >> b >> c;
		vec[a].push_back(make_pair(b, c));
		vec[b].push_back(make_pair(a, c));
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			dist[i][j] = 2000000000;
		dijkstra(i);
	}

	for (int i = 0; i < q; i++) {
		cin >> k >> v;
		int cnt = 0;
	
		for (int j = 1; j <= n; j++) {
			if (j == v)
				continue;
			if (dist[v][j] >= k)
				cnt++;
		}
		cout << cnt << "\n";
	}

	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << dist[i][j] << ' ';
		}
		cout << endl;
	}*/

	return 0;
}