задача 1336

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
n, m = map(int, input().split())
s, e = map(int, input().split())
a = [[-1.0]*n for i in range(n)]
for i in range(m):
b, c, l = map(int, input().split())
a[b-1][c-1] =1-l/100
a[c-1][b-1] =1-l/100
for k in range(n):
for i in range(n):
for j in range(n):
if i!=j:
a[i][j] = max(a[i][j], a[i][k]*a[k][j])
print(1-a[s-1][e-1])
'''
n, m = map(int, input().split())
s, e = map(int, input().split())
a = [[-1.0]*n for i in range(n)]
for i in range(m):
b, c, l = map(int, input().split())
a[b-1][c-1] =l/100
a[c-1][b-1] =l/100
for k in range(n):
for i in range(n):
for j in range(n):
if i!=j and a[i][k]>=0 and a[k][j]>=0 and (a[i][j]>1-(1-a[i][k])*(1-a[k][j]) or a[i][j]==-1.0):
a[i][j] = 1-(1-a[i][k])*(1-a[k][j])
print(a[s-1][e-1])
'''
'''
n, m = [int(s) for s in input().split()]
s, e = [int(s) for s in input().split()]
min_dist = [[float('+inf')]*n for i in range(n)]
for i in range(m):
a = [int(s) for s in input().split()]
min_dist[a[0]-1][a[1]-1] = a[2]/100
min_dist[a[1]-1][a[0]-1] = a[2]/100
for k in range(n):
for i in range(n):
for j in range(n):
if i == j:
min_dist[i][j] = 0
else:
if 1 - (1 - min_dist[i][k]) * (1 - min_dist[k][j]) > float('-inf'):
min_dist[i][j] = min(min_dist[i][j], 1 - (1 - min_dist[i][k]) * (1 - min_dist[k][j]))
print(min_dist[s-1][e-1])
'''