# 문제번호. 문제 제목 [링크](https://www.acmicpc.net/problem/1516) | 난이도 | 정답률(\_%) | | :----: | :---------: | | Gold II | 46 | ## 설계 ### 위상정렬 ## 정리 | 내 코드 | 빠른 코드 | | :-----: | :-------: | | 4 ms | | ## 고생한 점 ## code ```cpp #include <algorithm> #include <iostream> #include <string> #include <vector> #include <queue> using namespace std; void solution() { int N; cin >> N; vector<int> answers(N + 1, 0); vector<int> costs(N + 1); vector<vector<int> > graph(N + 1); vector<int> indegree(N + 1, 0); for (int i = 1; i <= N; i++) { int time, cur = 0; cin >> time; costs[i] = time; while (cin >> cur, cur!=-1) { graph[cur].push_back(i); indegree[i] += 1; } } queue<int> q; // find the roots for (int i = 1; i <= N; i++) { if (indegree[i] == 0) { q.push(i); answers[i] = costs[i]; } } while (!q.empty()) { int cur = q.front(); q.pop(); for (int next : graph[cur]) { answers[next] = max(answers[next], answers[cur] + costs[next]); indegree[next] -= 1; if (indegree[next] == 0) q.push(next); } } for (int i = 1; i < answers.size();i++) { cout << answers[i] << "\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solution(); return 0; } ```
Activity