CSES1686 收集金币
#CS1686. 收集金币
收集金币
题目背景
翻译自 CSES-1686 题。
题目描述
游戏中有 n 个房间，和 m 条隧道连接它们。每个房间中有一定数量的金币。你可以自由选择起始房间和结束房间，问题是：在通过隧道时，最多能收集到多少金币？
输入格式
第一行包含两个整数 n 和 m：分别表示房间的数量和隧道的数量。房间编号为 1,2,…,n1,2,…,n1,2,…,n。
接下来的一行包含 n 个整数 k1,k2,…,knk_1,k_2,…,k_nk1,k2,…,kn：表示每个房间中的金币数量。
接下来有 m 行，每行描述一条隧道。每行包含两个整数 a 和 b：表示从房间 a 到房间 b 有一条单向隧道。
输出格式
输出一个整数：表示你能收集到的最大金币数。
样例
4 4
4 5 2 7
1 2
2 1
1 3
2 4
16
说明/提示
1≤ki≤1091 \leq k_i \leq 10^91≤ki≤109；