往届 ACM 队训练题 (参考)

1083. 小强过桥

单点时限: 5.0 sec

内存限制: 256 MB

给出一个无向图,N 个结点,M 条边。我要从 s 出发到 t, 每一条边是一座不稳定的桥,如果小强带的货物重量超过了桥的承重,小强就会掉到河里。小强最多能带多少货物呢?

输入格式

多组数据。每组数据以 N M(1<= N <= 100000,1<= M <= 1000000) 开始,下面 M 行,每行有三个整数,x y w(1<=x<=N,1<=y<=N,1<=w<=<=2,000,000,000),表示桥的起点、终点和承重。最后一行包含 s t 两个整数。

输出格式

对于每组数据,输出最大的重量。

样例

Input
6 6
1 5 2000
2 4 5000
2 5 3300
3 4 2400
3 6 2200
4 6 6000
3 5
Output
2400
不限期开放

题目列表