-
[PS] 백준 1005번: ACM Craft문제해결 2023. 10. 25. 17:21
이런저런 시도를 하는데 자꾸 4%에서 틀리더라.
그러다 그냥 dfs(W)만 하면 된다는걸 이해해버려서 dfs로 풀었다.
#include <bits/stdc++.h> #define endl "\n" #define FOR(a, n) for(int a = 0; a < int(n); a++) using namespace std; int get_total_time(int idx, vector<vector<int>> &prevs, vector<int>& time, vector<int>& total_time, vector<bool>& fixed) { if (fixed[idx]) return total_time[idx]; int MAX = 0; // 나한테 화살표 꽂고 있는 놈들 중에서 가장 오래걸리는 놈 찾기 FOR(i, prevs[idx].size()) MAX = max(MAX, get_total_time(prevs[idx][i], prevs, time, total_time, fixed)); fixed[idx] = true; total_time[idx] = MAX + time[idx]; return total_time[idx]; } void progress() { int N, K; cin >> N >> K; vector<int> time(N); FOR(i, N) { int t; cin >> t; time[i] = t; } // prevs: 나에게 화살표 꽂고 있는 놈들 vector<vector<int>> prevs(N); FOR(i, K) { int a, b; cin >> a >> b; a -= 1, b -= 1; prevs[b].push_back(a); } int target; cin >> target; target -= 1; vector<int> tt(N, 0); vector<bool> fixed(N, false); cout << get_total_time(target, prevs, time, tt, fixed) << endl; } int main() { int T; cin >> T; for (int CNT = 0; CNT < T; CNT++) progress(); }
'문제해결' 카테고리의 다른 글
[PS] 코드트리: 싸움땅 (0) 2023.10.25 [PS] 코드트리: 코드트리 빵 (0) 2023.10.25 [PS] 백준 21610번: 마법사 상어와 비바라기 (0) 2023.10.25 [PS] 백준 10630번: RLE Replacement (0) 2023.10.25 [PS] 백준 12865번: 평범한 배낭 (0) 2023.10.25