乌拉拉市有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 次询问的结果 输入样例: 3 2 5 1 2 3 2 3 3 2 3 2 1 3 输出样例: 0 1 输入样例: 4 0 1 1 2 1 输出样例: -1 样例1: 从3到2距离为3，更换电车 从1到3的道路是1->2->3，如果不在2更换，那就无法走到3，所以要换一次电车

这是一道最短路问题，但是与普通的最短路问题略有不同，需要记录更换电车的次数。可以使用 Dijkstra 算法来求解。

Dijkstra 算法的基本思路是从起点开始，依次扩展最短的边，直到扩展到终点或者所有点都被扩展。在这个过程中，需要记录从起点到每个点的最短距离和最短路径。

对于这道题目，我们可以对 Dijkstra 算法进行一些修改，记录从起点到每个点的最少更换电车次数和最短路径。在扩展边的时候，如果当前边需要更换电车，则更换电车次数加 1，否则继承之前的更换电车次数。

最后，对于每个询问，如果起点和终点不连通，则输出 -1，否则输出其最少更换电车次数。

时间复杂度

Dijkstra 算法的时间复杂度为 O(mlogn)，对于每个询问需要运行一遍 Dijkstra 算法，所以总的时间复杂度为 O(qmlogn)。

参考代码

相关问题

乌拉拉市有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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310;
const ll inf = 1e18;

int n, m, q;
ll L, dis[N][N];
struct Edge {
    int from, to;
    ll w;
    Edge(int a = 0, int b = 0, ll c = 0): from(a), to(b), w(c) {}
};
vector<Edge> edges;
vector<int> G[N];

void addEdge(int u, int v, ll w) {
    edges.push_back(Edge(u, v, w));
    int m = edges.size();
    G[u].push_back(m - 1);
}

void floyd() { // 预处理任意两点之间的最短路
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dis[i][j] = (i == j ? 0 : inf);
        }
    }
    for (int i = 0; i < edges.size(); ++i) {
        int u = edges[i].from, v = edges[i].to;
        dis[u][v] = dis[v][u] = min(dis[u][v], edges[i].w);
    }
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

int main() {
    scanf("%d%d%lld", &n, &m, &L);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        ll w;
        scanf("%d%d%lld", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    floyd(); // 预处理任意两点之间的最短路

    scanf("%d", &q);
    while (q--) {
        int s, t;
        scanf("%d%d", &s, &t);
        if (dis[s][t] > L) { // 如果直接走超过了L，无法到达
            printf("-1\n");
            continue;
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < G[i].size(); ++j) {
                int k = edges[G[i][j]].to;
                if (dis[s][i] + edges[G[i][j]].w + dis[k][t] <= L) { // 如果从i到k再到t的距离小于等于L，则可以不用换电车
                    ans = max(ans, 1);
                } else { // 否则需要在i处换电车
                    ans = max(ans, 2);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}