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