C - お金の街 (The Money Town)
Editorial
/
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
うさぎは、お金が大好きである。
うさぎは、ある都市を散策することにした。ただし、時間の関係上 同じ街を2度通ってはいけないが、どこの町から出発してもよい。
街 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が与えられる。
出力
出力は以下の形式で標準出力に行うこと。
うさぎが得られるお金の最大値を1行に出力しなさい。
ただし、答えは 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