[BOJ] 1516 게임개발

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

위상정렬을 하면서 자신의 건물 짓는 시간을 뒤에 연결된 노드들의 건물 짓는 시간에 더해야한다.

resTime[next] = resTime[cur]+bTime[next]

이때 이전에 계산한 시간과 위상 정렬을 하며 다시 계산된 시간중 큰것을 답으로 해야한다.

---

#include <queue>

#include <vector>

#include <algorithm>

using namespace std;

int main(){

int N;

vector<int> vec[501];

queue<int> q;

int bTime[501];

int resTime[501]={};

int line[501];

scanf("%d",&N);

int tp = 0;

for(int i = 1;i<=N;i++){

scanf("%d",&bTime[i]);

//resTime[i] = bTime[i];

while(true){

scanf("%d",&tp);

if(tp == -1) break;

vec[tp].push_back(i);

line[i]++;

}

}

for(int i = 1;i<=N;i++){

if(line[i] == 0){

q.push(i);

}

resTime[i] += bTime[i];

}

int cur;

while(!q.empty()){

cur = q.front();

q.pop();

for(int i = 0;i<vec[cur].size();i++){

int next = vec[cur][i];

resTime[next] = max(resTime[next],resTime[cur]+bTime[next]);

if(--line[next] == 0){

q.push(next);

}

}

}

for(int i = 1;i<=N;i++){

printf("%d\n",resTime[i]);

}

}