#188. [CQOI2015]网络吞吐量

[CQOI2015]网络吞吐量

[CQOI2015] 网络吞吐量

题目背景

路由是指通过计算机网络把信息从源地址传输到目的地址的活动,也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地,路由器需要选择最优的路径转发数据包。例如在常用的路由算法 OSPF (开放式最短路径优先) 中,路由器会使用经典的 Dijkstra 算法计算最短路径,然后尽量沿最短路径转发数据包。

题目描述

现在,若已知一个计算机网络中各路由器间的连接情况,以及各个路由器的最大吞吐量(即每秒能转发的数据包数量),网络中的路由器使用 11nn 编号,假设所有数据包一定沿最短路径转发,试计算从路由器 11 到路由器 nn 的网络的最大吞吐量。计算中忽略转发及传输的时间开销,不考虑链路的带宽限制,即认为数据包可以瞬间通过网络。路由器 11 到路由器 nn 作为起点和终点,自身的吞吐量不用考虑,网络上也不存在将 11nn 直接相连的链路。

输入格式

输入的第一行是用空格隔开的两个整数,分别代表路由器的数量 nn 和链路的数量 mm

22 到第 (m+1)(m + 1) 行,每行三个整数 u,v,wu, v, w,代表存在一条连结路由器 uu 和路由器 vv 的距离为 ww 的双向链路。

(m+2)(m + 2) 到第 (n+m+1)(n + m + 1) 行,每行一个整数,第 (i+m+1)(i + m + 1) 行的整数代表路由器 ii 的吞吐量 cic_i

输出格式

输出一行一个整数,代表网络的最大吞吐量。

样例 #1

样例输入 #1

7 10
1 2 2
1 5 2
2 4 1
2 3 3
3 7 1
4 5 4
4 3 1
4 6 1
5 6 2
6 7 1
1
100
20
50
20
60
1

样例输出 #1

70

提示

数据规模与约定

对于 100%100\% 的数据,保证 1n5001 \leq n \leq 5001m1051 \leq m \leq 10^51w,ci1091 \leq w, c_i \leq 10^9