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

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

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

 对于100%的数据，n≤500，m≤100000，d,c≤10^9

  1 #include <cstdio>  2 #include <cstring>  3   4 #define int long long  5    6 inline int nextChar(void) {  7     const int siz = 1024;  8     static char buf[siz];  9     static char *hd = buf + siz; 10     static char *tl = buf + siz; 11     if (hd == tl) 12         fread(hd = buf, 1, siz, stdin); 13     return *hd++; 14 } 15   16 inline int nextInt(void) { 17     register int ret = 0; 18     register int neg = false; 19     register int bit = nextChar(); 20     for (; bit < 48; bit = nextChar()) 21         if (bit == ‘-‘)neg ^= true; 22     for (; bit > 47; bit = nextChar()) 23         ret = ret * 10 + bit - 48; 24     return neg ? -ret : ret; 25 } 26   27 const int inf = 2e18; 28 const int siz = 1000005; 29   30 int n, m; 31   32 struct edge { 33     int x, y, w; 34 }e[siz]; 35   36 int lim[siz]; 37   38 namespace shortestPath  39 { 40     int dis[2][siz]; 41       42     int edges; 43     int hd[siz]; 44     int to[siz]; 45     int nt[siz]; 46     int vl[siz]; 47       48     inline void add(int u, int v, int w) { 49         nt[edges] = hd[u]; to[edges] = v; vl[edges] = w; hd[u] = edges++; 50         nt[edges] = hd[v]; to[edges] = u; vl[edges] = w; hd[v] = edges++; 51     } 52       53     inline void spfa(int *d, int s) { 54         static int que[siz]; 55         static int inq[siz]; 56         static int head, tail; 57         memset(inq, 0, sizeof(inq)); 58         for (int i = 0; i < siz; ++i)d[i] = inf; 59         inq[que[head = d[s] = 0] = s] = tail = 1; 60         while (head != tail) { 61             int u = que[head++], v; inq[u] = 0; 62             for (int i = hd[u]; ~i; i = nt[i]) 63                 if (d[v = to[i]] > d[u] + vl[i]) { 64                     d[v] = d[u] + vl[i]; 65                     if (!inq[v])inq[que[tail++] = v] = 1; 66                 } 67         } 68     } 69       70     inline void solve(void) { 71         memset(hd, -1, sizeof(hd)); 72         for (int i = 1; i <= m; ++i) 73             add(e[i].x, e[i].y, e[i].w); 74         spfa(dis[0], 1); 75         spfa(dis[1], n); 76     } 77 } 78   79 namespace networkFlow  80 { 81     int s, t; 82     int edges; 83     int hd[siz]; 84     int to[siz]; 85     int nt[siz]; 86     int fl[siz]; 87       88     inline void add(int u, int v, int f) { 89         nt[edges] = hd[u]; to[edges] = v; fl[edges] = f; hd[u] = edges++; 90         nt[edges] = hd[v]; to[edges] = u; fl[edges] = 0; hd[v] = edges++; 91     } 92       93     int dep[siz]; 94       95     inline bool bfs(void) { 96         static int que[siz], head, tail; 97         memset(dep, 0, sizeof(dep)); 98         dep[que[head = 0] = s] = tail = 1; 99         while (head != tail) {100             int u = que[head++], v;101             for (int i = hd[u]; ~i; i = nt[i])102                 if (fl[i] && !dep[v = to[i]])103                     dep[que[tail++] = v] = dep[u] + 1;104         }105         return dep[t];106     }107      108     int lst[siz];109      110     int dfs(int u, int f) {111         if (u == t || !f)return f;112         int used = 0, flow, v;113         for (int i = lst[u]; ~i; i = nt[i])114             if (dep[v = to[i]] == dep[u] + 1) {115                 flow = dfs(v, f - used < fl[i] ? f - used : fl[i]);116                 used += flow;117                 fl[i] -= flow;118                 fl[i^1] += flow;119                 if (fl[i])lst[u] = i;120                 if (used == f)return f;121             }122         if (!used)dep[u] = 0;123         return used;124     }125      126     inline int maxFlow(void) {127         int maxFlow = 0, newFlow;128         while (bfs()) {129             for (int i = s; i <= t; ++i)130                 lst[i] = hd[i];131             while (newFlow = dfs(s, inf))132                 maxFlow += newFlow;133         }134         return maxFlow;135     }136      137     inline void solve(void) {138         s = 0, t = (n + 1) << 1;139         memset(hd, -1, sizeof(hd));140         add(s, 1 << 1, inf);141         add(n << 1 | 1, t, inf);142         for (int i = 1; i <= n; ++i)143             add(i << 1, i << 1 | 1, lim[i]);144         for (int i = 1; i <= m; ++i) {145             int x, y, d = shortestPath::dis[0][n];146             x = shortestPath::dis[0][e[i].x];147             y = shortestPath::dis[1][e[i].y];148             if (x + y + e[i].w == d)149                 add(e[i].x << 1 | 1, e[i].y << 1, inf);150             x = shortestPath::dis[0][e[i].y];151             y = shortestPath::dis[1][e[i].x];152             if (x + y + e[i].w == d)153                 add(e[i].y << 1 | 1, e[i].x << 1, inf);154         }155         printf("%lld\n", maxFlow());156     }157 }158  159 signed main(void) {160     n = nextInt();161     m = nextInt();162     for (int i = 1; i <= m; ++i)163         e[i].x = nextInt(),164         e[i].y = nextInt(),165         e[i].w = nextInt();166     for (int i = 1; i <= n; ++i)167         lim[i] = nextInt();168     lim[1] = lim[n] = inf;169     shortestPath::solve();170     networkFlow::solve();171 }