[AtCoder] CODE FESTIVAL 2018 Final (Parallel) A – 2540

問題

方針

与えられたグラフにおいて、\( 2 \) 回の移動で距離が \( 2540 \) となるパスの合計を求めたいので、ある頂点に接続している辺の距離の本数を数えます。

例えば、\(G[ i] [L] \) を頂点 \( i \) から延びる距離 \( L \) の辺の本数となります。これを利用して、\(G[i] [l] * G[i][2540 – l]\) を全ての頂点と距離について加算します。

ただし、辺の距離が \( 1270 \) となる頂点については、\( G[i][1270] * (G[i][1270] – 1) \) と計算する必要があります。これは、\( 1270 \) の距離をもつ辺から二つ選ぶ必要があるためです。

また、全てを加算した後に、\( 2 \) で除算する必要があります。これは、重複して加算してるからです。

コード

提出したコード

マップを利用した数え上げ