AcWing 1126. 最小花费(python3)
原题链接
简单
作者:
命不该绝
,
2023-10-07 07:36:51
,
所有人可见
,
阅读 77
from collections import deque
def spfa():
global A, B, g, st, d, n, m
q = deque()
q.append(A)
d[A] = 1
while q:
t = q.popleft()
st[t] = False
for i in range(1, n + 1):
if d[i] < d[t] * g[t][i]:
d[i] = d[t] * g[t][i]
if st[i] == False:
q.append(i)
st[i] = True
if __name__ == '__main__':
n, m = map(int, input().split())
g = [[0] * 2010 for i in range(2010)]
st = [False] * 2010
d = [0] * 2010
for i in range(m):
a, b, c = map(int, input().split())
t = (100 - c) / 100
g[a][b] = g[b][a] = max(g[a][b], t)
A, B = map(int, input().split())
spfa()
print('%.8f' %(100 / d[B]))