[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;