Study hard
(c++)백준 15591번: MooTube (Silver) 본문
[풀이]
bfs를 사용하여 USADO가 k이상인 비디오의 개수를 세 주었다.
※query마다 visited배열을 false로 초기화해야한다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Video {
int v;
int USADO;
};
int N, Q;
int p, q, r;
vector<Video>Moo[5001];
bool visited[5001];
//v와의 USADO가 k미만인 비디오 개수 반환
int bfs(int k, int v) {
queue<int>q;
q.push(v);
visited[v] = true;
int cnt = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int i = 0; i <Moo[v].size(); i++) {
int nv = Moo[v][i].v;
int nU = Moo[v][i].USADO;
if (nU < k || visited[nv])
continue;
visited[nv] = true;
cnt++;
q.push(nv);
}
}
return cnt;
}
int main() {
cin >> N >> Q;
for (int i = 0; i < N - 1; i++) {
cin >> p >> q >> r;
Moo[p].push_back({ q,r });
Moo[q].push_back({ p,r });
}
int k, v;
while (Q--) {
for (int i = 1; i <= N; i++)
visited[i] = false;
cin >> k >> v;
cout << bfs(k, v) << '\n';
}
return 0;
}
'백준 > DP' 카테고리의 다른 글
(c++) 백준 9252번: LCS 2 (0) | 2021.02.24 |
---|---|
(c++)백준 9251번: LCS (0) | 2021.02.24 |
(c++)백준 2163번: 초콜릿 자르기 (0) | 2020.09.22 |
(c++)백준 2616번: 소형기관차 (0) | 2020.09.20 |
(c++)백준 2281번: 데스노트 (0) | 2020.09.19 |