結果

問題 No.298 話の伝達
ユーザー gew1fw
提出日時 2025-06-12 19:08:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,510 bytes
コンパイル時間 319 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 55,688 KB
最終ジャッジ日時 2025-06-12 19:08:59
合計ジャッジ時間 2,212 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx])
    idx += 1
    m = int(data[idx])
    idx += 1
    
    in_edges = [[] for _ in range(n)]  # in_edges[B] stores tuples of (A, C)
    edges = [[] for _ in range(n)]     # edges[A] stores tuples of (B, C)
    indegree = [0] * n
    
    for _ in range(m):
        a = int(data[idx])
        idx += 1
        b = int(data[idx])
        idx += 1
        c = int(data[idx])
        idx += 1
        in_edges[b].append((a, c))
        edges[a].append((b, c))
        indegree[b] += 1
    
    # Topological sort
    queue = deque()
    for i in range(n):
        if indegree[i] == 0:
            queue.append(i)
    
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for (v, c) in edges[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    
    # Initialize probabilities
    prob = [0.0] * n
    prob[0] = 1.0  # Group 0 starts with probability 1.0
    
    for b in order:
        if b == 0:
            continue  # Skip group 0, as its probability is fixed
        product = 1.0
        for (a, c) in in_edges[b]:
            if a == 0:
                p_a = 1.0
            else:
                p_a = prob[a]
            product *= (1.0 - p_a * c / 100.0)
        prob[b] = 1.0 - product
    
    print("{0:.10f}".format(prob[n-1]))

if __name__ == "__main__":
    main()
0