[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 \) で除算する必要があります。これは、重複して加算してるからです。
コード
提出したコード
マップを利用した数え上げ
int N, M; cin >> N >> M; vector<map<int, int>> v(N); for (int i = 0; i < M; i++) { int A, B, L; cin >> A >> B >> L; v[A - 1][L]++; v[B - 1][L]++; } int ans = 0; for (int i = 0; i < N; i++) { for (auto j = v[i].begin(); j != v[i].end(); j++) { int l = j -> first; int t1 = j -> second; int t2 = v[i][2540 - l]; if (l == 1270) t1--; ans += t1 * t2; } } ans /= 2;
ディスカッション
コメント一覧
まだ、コメントがありません