3931: [CQOI2015]网络吞吐量

Description

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

Input

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

 

Output

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

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

 

　　这题我的做法是处理每个点的距离后不断BFS，BZOJ上测的是总时间所以过了，把其中BFS改成Dinic就可以过了。

1 //rp++  2 //#include 
      
         3   4 #include 
       
          5 #include 
        
           6 #include 
         
            7 using namespace std;  8 const long long maxn=10010,maxm=4000010;  9 long long INF=(long long)1e17; 10  11 long long cnt=1,fir[maxn],to[maxm],nxt[maxm],val[maxm],cap[maxm]; 12 long long n,m; 13 void addedge(long long a,long long b,long long c,long long v) 14 { 15     nxt[++cnt]=fir[a];to[cnt]=b; 16     cap[cnt]=c;val[cnt]=v;fir[a]=cnt; 17 } 18  19 long long dis[maxn]; 20 bool vis[maxn]; 21 long long path[maxn]; 22 long long q[maxn<<1],front,back; 23 void BFS(long long S,long long T) 24 { 25     front=back=1; 26     q[back++]=S; 27     dis[S]=0;vis[S]=true; 28     while(front