結果

問題 No.298 話の伝達
ユーザー lam6er
提出日時 2025-04-16 15:53:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,022 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 81,924 KB
実行使用メモリ 55,676 KB
最終ジャッジ日時 2025-04-16 15:54:28
合計ジャッジ時間 1,827 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, M = map(int, sys.stdin.readline().split())
    edges = [[] for _ in range(N)]  # edges[B] contains (A, C)
    adj = [[] for _ in range(N)]    # adj[A] contains (B, C)
    for _ in range(M):
        A, B, C = map(int, sys.stdin.readline().split())
        adj[A].append((B, C))
        edges[B].append((A, C))
    
    # Step 1: Find all nodes reachable from 0 using BFS
    visited = set()
    q = deque()
    q.append(0)
    visited.add(0)
    while q:
        u = q.popleft()
        for (v, _) in adj[u]:
            if v not in visited:
                visited.add(v)
                q.append(v)
    
    # If the target node N-1 is not reachable, output 0.0
    if (N-1) not in visited:
        print(0.0)
        return
    
    # Step 2: Compute in_degree for each node in the visited set
    in_degree = [0] * N
    for B in visited:
        for (A, _) in edges[B]:
            if A in visited:
                in_degree[B] += 1
    
    # Step 3: Topological sort
    order = []
    q = deque()
    # Initialize queue with nodes having in_degree 0 in the visited set
    for u in visited:
        if in_degree[u] == 0:
            q.append(u)
            order.append(u)
    
    while q:
        u = q.popleft()
        for (v, _) in adj[u]:
            if v not in visited:
                continue
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
                order.append(v)
    
    # Step 4: Calculate probabilities
    prob = [0.0] * N
    prob[0] = 1.0  # initial probability
    
    for u in order:
        if u == 0:
            continue  # already set
        p = 1.0
        for (A, C) in edges[u]:
            if A not in visited:
                continue
            contrib = prob[A] * (C / 100.0)
            p *= (1.0 - contrib)
        prob[u] = 1.0 - p
    
    # Output the result with sufficient precision
    print("{0:.10f}".format(prob[N-1]))

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