Table of contents

• Problem
• Time complexity
• Solution

# Problem

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

# Time complexity

$O(N^3)$

# Solution

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