P3171 [CQOI2015] Network Throughput

Routing is the activity of transferring information from a source address to a destination address through a computer network, and it is both a key and difficult part of network design. The hardware device that performs routing and forwarding in a network is called a router. To deliver packets to their destinations as quickly as possible, routers need to choose optimal paths to forward packets. For example, in the commonly used routing algorithm OSPF (Open Shortest Path First), routers use the classic Dijkstra algorithm to compute shortest paths and then forward packets along the shortest paths whenever possible.

Now, given the connectivity between routers in a computer network and the maximum throughput of each router (i.e., the number of packets it can forward per second), with routers numbered from $1$ to $n$, assume all packets are forwarded strictly along shortest paths. Compute the maximum throughput from router $1$ to router $n$. Ignore the time overhead of forwarding and transmission, and do not consider link bandwidth limits, i.e., assume packets can traverse the network instantaneously. Routers $1$ and $n$ serve as the source and destination, and their own throughputs are not considered. There is also no link that directly connects $1$ and $n$.

The first line contains two integers separated by a space, representing the number of routers $n$ and the number of links $m$. Lines $2$ to $(m + 1)$ each contain three integers $u, v, w$, indicating there is an undirected link connecting routers $u$ and $v$ with distance $w$. Lines $(m + 2)$ to $(n + m + 1)$ each contain one integer. The integer on line $(i + m + 1)$ represents the throughput $c_i$ of router $i$.

Output a single line containing one integer, representing the maximum throughput of the network.

Constraints For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 500$, $1 \leq m \leq 10^5$, and $1 \leq w, c_i \leq 10^9$. Translated by ChatGPT 5