結果
問題 | No.30 たこやき工場 |
ユーザー |
|
提出日時 | 2023-01-29 08:02:10 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 36 ms / 5,000 ms |
コード長 | 852 bytes |
コンパイル時間 | 84 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-06-29 06:41:00 |
合計ジャッジ時間 | 1,358 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
from collections import defaultdict, deque def topological_sort(N, edges): outs = defaultdict(list) ins = defaultdict(int) for v1, v2 in edges: outs[v1].append(v2) ins[v2] += 1 q = deque(v1 for v1 in range(N) if ins[v1] == 0) while q: v1 = q.popleft() yield v1 for v2 in outs[v1]: ins[v2] -= 1 if ins[v2] == 0: q.append(v2) N = int(input()) M = int(input()) edges = [] material = [[] for _ in range(N)] for _ in range(M): p, q, r = map(int, input().split()) p -= 1 r -= 1 edges.append((p, r)) material[r].append((p, q)) ans = [0] * N ans[N - 1] = 1 for x in reversed(list(topological_sort(N, edges))): for p, q in material[x]: ans[p] += q * ans[x] if material[x]: ans[x] = 0 print(*ans[:-1], sep='\n')