[백준 1516번] 게임 개발

[백준 1516번] 게임 개발

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include < iostream > #include < string > #include < algorithm > #include < queue > #include < vector > #include < stack > #include < utility > #include < climits > #include < deque > using namespace std ; int n; vector < int > adj[ 501 ]; int indegree[ 501 ]; int dist[ 501 ]; int takeTime[ 501 ]; void bfs() { queue < int > Q; for ( int i = 1 ; i < = n; i + + ) { if (indegree[i] = = 0 ) { Q.push(i); dist[i] = takeTime[i]; } } while ( ! Q.empty()) { int u = Q. front (); Q. pop (); for ( auto & v : adj[u]) { dist[v] = max(dist[v], dist[u] + takeTime[v]); indegree[v] - - ; if (indegree[v] = = 0 ) { Q.push(v); } } } } int main( void ) { ios::sync_with_stdio( false ); cin .tie(nullptr); cin > > n; for ( int v = 1 ; v < = n; v + + ) { int t; cin > > t; takeTime[v] = t; while ( true ) { int u; cin > > u; if (u = = - 1 ) break ; adj[u]. push_back (v); indegree[v] + + ; } } bfs(); for ( int i = 1 ; i < = n; i + + ) { cout < < dist[i] < < '

' ; } return 0 ; } Colored by Color Scripter

from http://seokjin2.tistory.com/92 by ccl(A) rewrite - 2021-12-20 13:27:01