結果

問題 No.30 たこやき工場
ユーザー lam6er
提出日時 2025-03-26 15:48:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 72 ms / 5,000 ms
コード長 1,028 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 82,784 KB
実行使用メモリ 72,764 KB
最終ジャッジ日時 2025-03-26 15:49:51
合計ジャッジ時間 1,891 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque

n = int(input())
m = int(input())

recipe = defaultdict(list)
graph = defaultdict(list)
in_degree = [0] * (n + 1)  # 1-based indexing

for _ in range(m):
    P, Q, R = map(int, input().split())
    recipe[R].append((P, Q))
    graph[R].append(P)
    in_degree[P] += 1

# Topological sort
queue = deque()
for i in range(1, n + 1):
    if in_degree[i] == 0:
        queue.append(i)

top_order = []
while queue:
    u = queue.popleft()
    top_order.append(u)
    for v in graph[u]:
        in_degree[v] -= 1
        if in_degree[v] == 0:
            queue.append(v)

required = [0] * (n + 1)
required[n] = 1  # Final product N requires 1 unit

for u in top_order:
    if u in recipe:
        for (P, Q) in recipe[u]:
            required[P] += required[u] * Q

# Determine which products need to be purchased
result = []
for i in range(1, n):
    if i in recipe and len(recipe[i]) > 0:
        result.append(0)
    else:
        result.append(required[i])

for s in result:
    print(s)
0