atcoder

# # Time complexity

$O(N^3)$

# # Solution

#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();
} Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!