結果

問題 No.30 たこやき工場
ユーザー rpy3cpprpy3cpp
提出日時 2015-08-08 15:34:32
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 21 ms / 5,000 ms
コード長 1,679 bytes
コンパイル時間 557 ms
コンパイル使用メモリ 10,980 KB
実行使用メモリ 8,320 KB
最終ジャッジ日時 2023-08-23 05:15:41
合計ジャッジ時間 1,252 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 17 ms
8,100 KB
testcase_01 AC 16 ms
8,148 KB
testcase_02 AC 16 ms
8,092 KB
testcase_03 AC 16 ms
8,116 KB
testcase_04 AC 16 ms
8,140 KB
testcase_05 AC 17 ms
8,092 KB
testcase_06 AC 16 ms
8,088 KB
testcase_07 AC 16 ms
8,136 KB
testcase_08 AC 17 ms
8,320 KB
testcase_09 AC 17 ms
8,308 KB
testcase_10 AC 21 ms
8,032 KB
testcase_11 AC 16 ms
8,280 KB
testcase_12 AC 17 ms
8,000 KB
testcase_13 AC 16 ms
8,100 KB
testcase_14 AC 17 ms
8,292 KB
testcase_15 AC 17 ms
8,300 KB
testcase_16 AC 17 ms
8,308 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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