結果

問題 No.298 話の伝達
ユーザー gew1fw
提出日時 2025-06-12 14:06:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,053 bytes
コンパイル時間 339 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 56,348 KB
最終ジャッジ日時 2025-06-12 14:07:29
合計ジャッジ時間 1,756 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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[A] contains (B, C)
    reverse_edges = [[] for _ in range(n)]  # reverse_edges[B] contains (A, C)

    for _ in range(m):
        a, b, c = map(int, sys.stdin.readline().split())
        edges[a].append((b, c))
        reverse_edges[b].append((a, c))

    # Determine reachable nodes from group 0 using BFS
    reachable = [False] * n
    q = deque([0])
    reachable[0] = True
    while q:
        u = q.popleft()
        for (v, _) in edges[u]:
            if not reachable[v]:
                reachable[v] = True
                q.append(v)

    # If the target group is not reachable, output 0.0
    if not reachable[n-1]:
        print("0.0")
        return

    # Collect subgraph nodes and their incoming edges
    sub_nodes = [u for u in range(n) if reachable[u]]
    in_degree = {u: 0 for u in sub_nodes}
    sub_reverse_edges = {u: [] for u in sub_nodes}

    for b in sub_nodes:
        for (a, c) in reverse_edges[b]:
            if reachable[a]:
                sub_reverse_edges[b].append((a, c))
                in_degree[b] += 1

    # Perform topological sort on the subgraph
    top_order = []
    q = deque()
    for u in sub_nodes:
        if in_degree[u] == 0:
            q.append(u)

    while q:
        u = q.popleft()
        top_order.append(u)
        for (v, _) in edges[u]:
            if reachable[v]:
                if v in in_degree:
                    in_degree[v] -= 1
                    if in_degree[v] == 0:
                        q.append(v)

    # Calculate probabilities
    prob = [0.0] * n
    prob[0] = 1.0

    for u in top_order:
        if u == 0:
            continue
        product = 1.0
        for (a, c) in sub_reverse_edges.get(u, []):
            product *= (1.0 - prob[a] * c / 100.0)
        prob[u] = 1.0 - product

    # Output the result with sufficient precision
    print("{0:.10f}".format(prob[n-1]))

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