← 返回题目列表

AtCoder · s8pc_1_c

C. 金钱之城

中文机器翻译题面 查看原题

問題文

兔子非常喜欢金钱。

兔子决定在某个城市进行散步。然而,每条街道只能走一次,但可以从任意城市出发。

街 i 有的钱是 D_i 日元, 兔子想尽可能多地获取金钱。

请计算兔子能获取的最大金额。

不过,城市共有 N 个,道路共有 K 条, 道路 i 连接着城市 X_i和 按字典顺序比较 Y_i,而且道路是双向通行的。


入力

输入是按以下格式从标准输入给出的。

N K
D_1
D_2
:
D_N
X_1 Y_1
X_2 Y_2
:  :
X_K Y_K
  • 1 行包含一个整数 N 和 按字典顺序比较 K。 表示
  • 下一步 N 行包含了城市i 的金钱数 D_i 。 表示
  • 以及下一行 K 行包含X_i 和 按字典顺序比较Y_i。 表示

出力

应按以下格式输出到标准输出。 新道路建成后所有可能城市之间的最短路线长度之和,直至

兔子能够获得的最大金额,请在一行中输出。

但是,答案可能 32 不适合比特整数类型。

制約

  • 1≦N≦50
  • 1≦K≦50
  • 1≦D_i≦1,000,000,000
  • 1≦X_i, Y_i≦N
  • X_i≠Y_i
  • 已保证不存在相同的道路。
  • 可能的散步路线是2,000,000不超过通行道。

部分点

这个问题设有部分分数。

1≦N,K≦10如果对满足条件的测试用例全部答对,将给予50分。

如果对剩下的所有数据集全部答对,将给予50分。


入力例1

6 6
1
2
3
4
5
7
1 2
1 3
1 6
2 4
3 4
4 5

出力例1

20

街 6 从……出发,6→1→3→4→5 按……顺序走将会得到 7+1+3+4+5=20一个圆。


入力例2

4 2
1
10
5
6
1 2
3 4

出力例2

11

入力例3

5 4
2
3
5
6
7
1 3
1 4
2 4
4 5

出力例3

20

问题文承担者:E869120