글 읽기 - 58%에서 틀립니다 ㅠ 반례 좀 찾아주실 수 있으실까요?

ansubeom0 1년 전 0

목표 건물에서부터 첫 건물까지 역순으로 건설 건물 리스트를 뽑고, 위상정렬을 통해 시간을 구해내는 방식으로 구현했습니다.

58%에서 자꾸 틀리는데 도대체가 이유를 모르겠습니다 ㅠ

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    building, rule_cnt = map(int,input().split())
    build_times = list(map(int,input().split()))
    rule = {}
    for i in range(1,building+1):
        rule[i] = set()
    for _ in range(rule_cnt):
        prev, next = map(int,input().split())
        rule[prev].add(next)
    target = int(input())
    q = {target}
    tmp = sys.maxsize
    queue = {target}
    time = 0
    built = set()
    while len(q) != tmp:
        tmp = len(q)
        for i in rule:
            if len(q.intersection(rule[i])):
                q.add(i)
    for i in rule:
        rule[i] = q.intersection(rule[i])
    while queue:
        for i in rule:
            rule[i] -= queue
        time += max([build_times[i - 1] for i in queue])
        built = built.union(queue)
        queue = set()
        for i in q:
            if rule[i] == set() and i not in built:
                queue.add(i)
    print(time)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

58%에서 틀립니다 ㅠ 반례 좀 찾아주실 수 있으실까요?

ansubeom0 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말