Problem
Problem URL : 게임 개발
Code
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<vector<int>> v;
int cost[501];
int idg[501]; // idg is indegree
int cost_dp[501];
int main(){
int n;
cin >> n;
v.resize(n+1);
for(int i=1; i<=n; i++){
int value;
cin >> value;
cost[i] = value;
while (1) {
int a;
scanf("%d",&a);
if( a == -1 ) break;
v[a].push_back(i);
idg[i] ++;
}
}
queue<int> q;
for(int i=1; i<=n; i++){
if( idg[i] == 0){
q.push(i);
cost_dp[i] = cost[i];
}
}
while (! q.empty()) {
int top = q.front();
q.pop();
int size = (int) v[top].size();
for(int i=0; i<size; i++){
int next = v[top][i];
if( cost_dp[next] < cost_dp[top] + cost[next])
cost_dp[next] = cost_dp[top] + cost[next];
if ( --idg[next] == 0 )
q.push(next);
}
}
for(int i=1; i<=n; i++){
printf("%d\n",cost_dp[i]);
}
return 0;
}
Feed Back
-
위상 정렬(topological sort) 관련 문제 !
-
위상 정렬 문제 도가 튼거 같은 느낌이다 ㅎㅂㅎ