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
- Unreal Engine 5
- 투 포인터
- 정렬
- 그리디 알고리즘
- Team Fortress 2
- 알고리즘
- 백트래킹
- XR Interaction Toolkit
- 다익스트라
- 스택
- 트리
- 재귀
- 수학
- 우선순위 큐
- ue5
- DFS
- VR
- 누적 합
- 다이나믹 프로그래밍
- 그래프
- 자료구조
- 유니티
- 구현
- 브루트포스
- BFS
- 문자열
- 백준
- 유니온 파인드
- c++
- 시뮬레이션
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 |