Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 백트래킹
- 브루트포스
- 투 포인터
- 유니티
- 시뮬레이션
- 스택
- 다익스트라
- 유니온 파인드
- XR Interaction Toolkit
- 구현
- BFS
- 문자열
- 그리디 알고리즘
- c++
- 정렬
- VR
- 자료구조
- ue5
- 우선순위 큐
- DFS
- 트리
- Unreal Engine 5
- 알고리즘
- 그래프
- 수학
- 누적 합
- Team Fortress 2
- 재귀
- 백준
- 다이나믹 프로그래밍
Archives
- Today
- Total
1일1알
백준 15591번 MooTube (Silver) C++ 본문
https://www.acmicpc.net/problem/15591
15591번: MooTube (Silver)
농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의
www.acmicpc.net
bfs
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>
using namespace std;
using int64 = long long;
vector<vector<pair<int, int>>> graph;
vector<bool> found;
int n, q;
void RefreshFound() { for (auto a : found) a = false; }
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> q;
graph = vector<vector<pair<int, int>>>(n + 1, vector<pair<int, int>>());
found = vector<bool>(n + 1, false);
for (int i = 0; i < n - 1; i++) {
int p, q, r;
cin >> p >> q >> r;
graph[p].push_back({ q,r });
graph[q].push_back({ p,r });
}
for (int i = 0; i < q; i++) {
int k, v;
cin >> k >> v;
int cnt = 0;
queue<pair<int, int>> q;
q.push({ v,1000000001 });
found[v] = true;
while (!q.empty()) {
auto curr = q.front();
q.pop();
if (curr.second >= k && curr.first != v) cnt++;
for (auto next : graph[curr.first]) {
if (found[next.first]) continue;
found[next.first] = true;
q.push({ next.first,min(curr.second,next.second) });
}
}
RefreshFound();
cout << cnt << "\n";
}
}
'알고리즘' 카테고리의 다른 글
백준 8911번 거북이 C++ (0) | 2022.11.16 |
---|---|
백준 15565번 귀여운 라이언 C++ (0) | 2022.11.15 |
백준 12919번 A와 B 2 C++ (0) | 2022.11.13 |
백준 13164번 행복 유치원 C++ (0) | 2022.11.12 |
백준 1956번 운동 C++ (0) | 2022.11.11 |