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

2540

https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_a

グラフの問題というよりか、数え上げの問題だと思います。

考え方

題意

与えられたグラフにおいて、\( 2 \) 回の移動で距離が \( 2540 \) となるパスの合計を答えます。

方針

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

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

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

コード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする