結果
問題 | No.30 たこやき工場 |
ユーザー |
|
提出日時 | 2022-03-02 15:13:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 67 ms / 5,000 ms |
コード長 | 717 bytes |
コンパイル時間 | 318 ms |
コンパイル使用メモリ | 82,336 KB |
実行使用メモリ | 72,328 KB |
最終ジャッジ日時 | 2024-07-16 08:08:47 |
合計ジャッジ時間 | 1,976 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
N = int(input()) M = int(input()) G = [[] for _ in range(N+1)] rG = [[] for _ in range(N+1)] Gnum = [0] * (N + 1) for _ in range(M): p,q,r = map(int,input().split()) G[p].append(r) rG[r].append((p,q)) Gnum[r] += 1 top = [] gaibu = set() from collections import deque q = deque() for i in range(1,N+1): if Gnum[i] == 0: q.append(i) gaibu.add(i) while q: now = q.popleft() top.append(now) for v in G[now]: Gnum[v] -= 1 if Gnum[v] == 0: q.append(v) dp = [0] * (N+1) dp[N] = 1 for now in reversed(top): for v,c in rG[now]: dp[v] += dp[now] * c for i in range(1,N): if i in gaibu: print(dp[i]) else: print(0)