[1516] 게임 개발

https://www.acmicpc.net/problem/1516

1516번: 게임 개발

<문제>

위상정렬을 사용했다.

dist[]가 최적해를 저장하는 배열, cur이 현재 정점, next가 cur과 연결된 정점, a[]가 각 정점의 가중치일때

각 건물을 짓기까지 걸리는 시간은 dist[next]=max(dist[cur]+a[next], dist[next])로 표현된다.

그 외에는 기본적인 위상정렬과 동일하다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, dist[501], ind[501], a[501];
vector<int> adj[501];
queue<int> q;
int main(void) {
    int i, j;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> a[i];
        while (1) {
            int x;
            cin >> x;
            if (x == -1) break;
            adj[x].push_back(i);
            ind[i]++;
        }
    }
    for (i = 1; i <= n; i++)
        if (ind[i] == 0) {
            q.push(i);
            dist[i] = a[i];
        }
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto& next : adj[cur]) {
            ind[next]--;
            dist[next] = max(dist[cur] + a[next], dist[next]);
            if (ind[next] == 0) q.push(next);
        }
    }
    for (i = 1; i <= n; i++) cout << dist[i] << '\n';
    return 0;
}