TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3250
  • Problem
  • P3250【CQOI2015】网络吞吐量
    Limits : Time Limit : 10000 MS   Memory Limit : 524288 KB
    Description

            路由是指通过计算机网络把信息从源地址传输到目的地址的活动,也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地,路由器需要选择最优的路径转发数据包。例如,在常用的路由算法OSPF(开放式最短路径优先)中,路由器会使用经典的Dijkstra算法计算最短路径,然后尽量沿最短路径转发数据包。
            现在,若已知一个计算机网络中各路由器间的连接情况,以及各个路由器的最大吞吐量(即每秒能转发的数据包数量),假设所有数据包一定沿最短路径转发,试计算从路由器1到路由器n的网络的最大吞吐量。计算中忽略转发及传输的时间开销,不考虑链路的带宽限制,即认为数据包可以瞬间通过网络。路由器1到路由器n作为起点和终点,自身的吞吐量不用考虑,网络上也不存在将1和n直接相连的链路。

    Input Format

            输入文件第一行包含两个空格分开的正整数n和m,分别表示路由器数量和链路的数量。网络中的路由器使用1到n编号。
            接下来m行,每行包含三个空格分开的正整数a,b和d,表示从路由器a到路由器b存在一条距离为d的双向链路。
            接下来n行,每行包含一个正整数c,分别给出每一个路由器的吞吐量。

    Output Format

            输出一个整数,为题目所求吞吐量。

    Sample Input

    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

    Sample Output

    70

    Hint

    样例解释


    数据范围
            对于30%的数据,n≤100,m≤1000。
            对于100%的数据,n≤500,m≤100000,d,c≤109