結果

問題 No.30 たこやき工場
コンテスト
ユーザー rpy3cpp
提出日時 2015-08-08 15:34:32
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 36 ms / 5,000 ms
コード長 1,679 bytes
コンパイル時間 99 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2024-12-21 05:19:55
合計ジャッジ時間 1,399 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def read_data():
    '''投入行列をmatとし、
    mat[p][r] = q 製品 r を作るのに材料 p が q 個必要  
    '''
    N = int(input())
    M = int(input())
    mat = [dict() for n in range(N)]
    matrev = [dict() for n in range(N)]
    for m in range(M):
        p, q, r = map(int, input().split())
        mat[p - 1][r - 1] = q
        matrev[r - 1][p - 1] = q
    return N, mat, matrev


def solve(N, mat, matrev):
    '''
    topological sort して、dp で埋めていく。
    外部から調達が必要なのは、原料が示されていないものになる。
    '''
    order = topological_sort(mat)
    qs = [0] * N
    qs[N-1] = 1
    for product in order[::-1]:
        q0 = qs[product]
        for material, q in matrev[product].items():
            qs[material] += q0 * q
    result = [(0 if matrev[i] else q) for i, q in enumerate(qs)]
    return result


def topological_sort(Es):
    def bfs(s):
        nonlocal notyet, in_degree, result, Es
        que = [s]
        notyet[s] = False
        while que:
            u = que.pop()
            result.append(u)
            for v in Es[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0 and notyet[v]:
                    notyet[v] = False
                    que.append(v)                      
    N = len(Es)
    notyet = [True] * N
    in_degree = [0] * N
    result = []
    for src, dsts in enumerate(Es):
        for dst in dsts:
            in_degree[dst] += 1
    for u in range(N):
        if in_degree[u] == 0 and notyet[u]:
            bfs(u)
    return result

N, mat, matrev = read_data()
result = solve(N, mat, matrev)
for q in result[:-1]:
    print(q)
0