目次

• 問題
• 解説
• 計算量
• 解答

# 問題

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

# 解説

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

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

# 計算量

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

$O(N^3)$

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#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();
}