7849 - 试题J:传递信息 25'

通过次数

10

提交次数

186

时间限制 : 5 秒
内存限制 : 512 MB

传话游戏

规则:每组的第一位同学看到30秒纸条, 再把纸条上写的内容传给第1二个同学,依次传下去,最后一个同学把听到的内容写到黑板上,传话最快最准确的一组获胜

我们知道在传话过程中不可避免会因为一些表述的问题使得传递的信息不够准确,我们将此暂定为噪声,并规定其存在噪声值。噪声值越小表示传递的信息越准确。

通过这个游戏我们开始思考另一个问题,现在有n个同学在一个广 场上,他们将分别对他们的伙伴传话(这里考虑a认为b是他的伙伴,b并不一定认为a是他的伙伴), 我们考虑当ab传话的噪声值为xbc传话的噪声值是y,那么如果a想传话给c其噪声值是x*y

现在s同学想把信息传递给t同学,当然我们希望传递到同学时信息尽可能完整,

那么s传到t的噪声我们希望是最小的。

输入

1行输入四个正整数n, m, s, t (m表示有多少种传话的方式)

2m+1行每行输入三个正整数u, v, w分别表示u同学,v同学,u传话给v所造成的噪声值w

输入保证没有自环,可能存在重边

输出

输出一个整数, 表示s传话给t最小的噪声值

s无法给t传话,则输出-1

样例

输入

4 4 1 3
1 2 8
1 3 65536
2 4 2
4 3 16

输出

256

提示

数据规模

对于30\%的数据:

1≤n≤10,1≤m≤10^2,1≤u,v≤n,1≤w≤64

对于60\%的数据:

1≤n≤10^3,1≤m≤10^4,1≤u,v≤n,1≤w≤4096

对于80\%的数据:

1≤n≤5*10^3,1≤m≤10^4,1≤u,v≤n,1≤w≤1024

对于100\%的数据:

1≤n≤5*10^4,1≤m≤10^5,1≤u,v≤n,1≤w≤10^{10}

其中w一定是2的整数次幂

 

来源

竞码编程-蓝桥杯校内选拔赛(决赛)重现赛