概率题

题目一

题目链接

https://www.acwing.com/problem/content/description/219/

题目大意

题目代码

from sys import stdin,setrecursionlimit
from functools import lru_cache
from math import inf
from collections import defaultdict as df
from collections import deque
setrecursionlimit(1000000)
input = lambda: stdin.readline().strip()

r1 = lambda: int(input())
r2 = lambda: map(int,input().split())
r3 = lambda: [*map(int,input().split())]

def solve():
    n,m = r2()
    g = df(list) 
    d = [0] * (n + 1)
    for _ in range(m):
        u,v,w = r2()
        g[u].append([v,w])
        d[u] += 1
    # dfs(u)表示从 u -> n 的期望长度
    '''
    爆栈喽！
    @lru_cache(None)
    def dfs(u):
        ans = 0
        for v,w in g[u]:
            ans += (w + dfs(v)) / d[u]
        return ans
    '''
    ans = 0
    q = deque([(1,1,0)])
    while q:
        u,p,dis = q.popleft()
        for v,w in g[u]:
            new_p = p * d[u]
            new_dis = dis + w
            if v == n:
                ans += new_dis / new_p
            else:
                q.append((v,new_p,new_dis))
            
    print("%.2f" % ans)
    
if __name__ == "__main__":

    t = 1
    for _ in range(t):
        solve()