백준(BOJ) 1005 ACM Craft(Python)

문제 내용.

 

위상 정렬 문제.

일반적인 위상 정렬을 진행하되, DP를 이용해 각 노드까지 이동할 때 걸리는 시간을 갱신해줬다.

진입 차수가 0인 노드부터 시작해서 해당 노드의 건설 시간+해당 노드까지 이동할 때 걸리는 시간과 다음 노드까지 걸리는 현재 시간 중 더 큰 것으로 DP를 갱신했다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
from itertools import combinations
from itertools import permutations
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

for _ in range(int(input())):
    n,k=map(int,input().split())
    L=[0]+list(map(int,input().split()))
    D=[[] for i in range(n+1)]
    V=[[0,0] for i in range(n+1)]
    for i in range(k):
        x,y=map(int,input().split())
        D[x].append(y)
        V[x][1]+=1
        V[y][0]+=1
    w=int(input())
    DP=[0 for i in range(n+1)]
    queue=deque()
    for i in range(1,n+1):
        if V[i][0]==0:
            queue.append(i)
    while queue:
        p=queue.popleft()
        for i in D[p]:
            DP[i]=max(DP[i],DP[p]+L[p])
            V[i][0]-=1
            if V[i][0]==0:
                queue.append(i)
    print(DP[w]+L[w])

위상 정렬을 몰라서 헤매다가 위상 정렬을 공부한 뒤 바로 풀었다.

코드가 오래 걸려서 썩 만족스럽진 않다.