TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3250
  • 题目
  • P3250【CQOI2015】网络吞吐量
    限制 : 时间限制 : 10000 MS   空间限制 : 524288 KB
    问题描述

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

    输入格式

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

    输出格式

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

    样例输入

    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

    样例输出

    70

    提示

    样例解释


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