非負重み付き無向グラフ ワーシャルフロイド法 グラフ理論 atcoder

Atcoder Beginner Content 143 E - Travel by Car

Atcoder Beginner Content 143 E - Travel by Car
Feb. 2, 2020, 1:52 p.m.

目次

問題

https://atcoder.jp/contests/abc143/tasks/abc143_e

解説

問題文から非負重み付き無向グラフであることを読み取る.
各都市間の最短距離がわかれば消費するガソリンは決定されるので、全点対間最短距離をワーシャルフロイド法によりもとめる.
なので、グラフは隣接行列で表現する(以降、G).
到達不可能なものは$\infty$とする.

もう一つ都市間移動で必要な給油の回数を記録する隣接行列(以降、COUNT)を作成し、Gをもとにタンクの大きさL以下で移動できるものを1とする.
その他は$\infty$.
COUNTに対してもう一度ワーシャルフロイドを適用し、全都市間の最小給油数を求める.

計算量

最も重い計算は2回あるワーシャルフロイドなので、$O(2N^3)$となる.

$O(N^3)$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#define MAX_N 301
#define MAX_Q (301*300)
#define MAX_C 1000000001

Int N, M, Q;
vector<Int> S(MAX_Q, -1), T(MAX_Q, -1);
ll L;

ll G[MAX_N][MAX_N];
ll COUNT[MAX_N][MAX_N];

void apsp(ll g[MAX_N][MAX_N]) {
  loop(k,0,N) {
    loop(u,0,N) {
      if (g[u][k] == MAX_C) continue;
      loop(v,0,N) {
        if (g[k][v] == MAX_C) continue;
        g[u][v] = min(g[u][v], g[u][k] + g[k][v]);
      }
    }
  }
}

void input() {
  Int a, b;
  ll c;
  cin >> N >> M >> L;
  loop(n,0,N) {
    loop(m,0,N) {
      G[n][m] = COUNT[n][m] = (n == m) ? 0 : MAX_C;
    }
  }

  loop(m,0,M) {
    cin >> a >> b >> c;
    G[a-1][b-1] = c;
    G[b-1][a-1] = c;
  }

  cin >> Q;
  loop(q,0,Q) {
    cin >> S[q] >> T[q];
    S[q]--;
    T[q]--;
  }
}

void solve() {
  apsp(G);
  loop(n,0,N) {
    loop(m,0,N) {
      if (G[n][m] <= L) COUNT[n][m] = 1;
    }
  }
  apsp(COUNT);
  loop(q,0,Q) {
    if (COUNT[S[q]][T[q]] == MAX_C) cout << -1 << endl;
    else cout << COUNT[S[q]][T[q]] - 1 << endl;
  }
}

int main() {
  input();
  solve();
}