乌拉拉市有n个共享电车桩点和m条双向道路，第 i 条道路连接 a i ​ 和 b i ​ ，长度为 c i ​ 单位距离。计算鸭每次使用一辆共享电车可以行驶 L 单位距离。更换共享电车只能在n个共享电车桩点更换，不能在路上更换，因为路上没有共享电车桩点。 现在计算鸭现在在规划行程，他有 q 个问题想要问你，第 i 个问题是：在s i ​ 点扫码租一辆共享电车后，想要到达t i ​ ，路途中，计算鸭最少需要更换几次共享电车，如果无法到达就是 −1。第一行输入三个整数 n,m,L，含义如题所示 接下来 m 行，每行输入三个正整数 a i ​ ,b i ​ ,c i ​ ，含义如题所示 然后在一行中输入一个正整数 q，代表询问的次数 最后 q 行，每行输入两个正整数 s i ​ ,t i ​ ，含义如题所示 2≤n≤300 0≤m≤ 2 n×(n−1) ​ 1≤a i ​ ,b i ​ ,s i ​ ,t i ​ ≤n 1≤L,c i ​ ≤10 9 1≤q≤n×(n−1) 输入保证无重边和自环； 询问中 s i ​  =t i ​。输出共 q 行，第 i 行代表第 i 次询问的结果。给出C++代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 310, M = 2 * N * N;

int n, m, L, Q;
int h[N], e[M], ne[M], w[M], idx;
int d[N][N];

struct Node {
    int x, y, z;
}nodes[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, w[idx] = c, ne[idx] = h[b], h[b] = idx ++;
}

void floyd() {
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main() {
    memset(d, 0x3f, sizeof d);
    cin >> n >> m >> L;
    for (int i = 0; i < m; i ++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    for (int i = 1; i <= n; i ++ )
        d[i][i] = 0;
    floyd();
    cin >> Q;
    while (Q -- ) {
        int s, t;
        cin >> s >> t;
        if (d[s][t] > L) {
            puts("-1");
            continue;
        }
        int res = 0;
        for (int i = 0; i < n; i ++ ) {
            for (int j = 0; j <= i; j ++ ) {
                if (d[s][nodes[i].x] + nodes[i].y + nodes[j].y + d[nodes[j].x][t] <= L)
                    res = max(res, nodes[i].z + nodes[j].z);
            }
        }
        cout << res << endl;
    }
    return 0;
}