乌拉拉市有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;
}

git本地分支和远程分支分开

### 如何在 Git 中分离本地分支与远程分支或独立操作

为了使本地分支与远程分支分离或能够独立操作，可以采取几种方法来实现这一目标。

#### 创建新的本地分支而不跟踪任何远程分支
创建一个新的本地分支并切换到该分支上工作而不需要关联任何现有的远程分支。这可以通过指定 `-b` 参数以及新分支名称完成：

git checkout -b new-feature-branch

此时的新分支 `new-feature-branch` 将不会自动追踪任何远程分支[^2]。

#### 停止跟踪当前的远程分支
如果已经在某个分支上并且希望停止与其对应的远程分支之间的联系，则可以在 `.git/config` 文件中手动编辑配置项或者通过命令行移除上游设置:

git branch --unset-upstream

这条指令会取消当前分支对于远程分支的跟踪关系，使得之后的操作不再同步至远端服务器上的相应位置[^1]。

#### 修改已有的本地分支使其不跟随特定的远程分支更新
当执行拉取(`pull`)或其他涉及获取最新更改的动作时，默认情况下可能会尝试从默认定义好的源处抓取数据。为了避免这种情况发生，在进行这些动作之前先确保指定了确切的目标地址而不是依赖于预设路径；也可以改变分支默认推送和拉取策略为简单模式(simple)，这样只有同名的情况下才会建立连接：

git config --global push.default simple

另外一种方式是在每次交互前都显式声明所要作用的对象，比如仅限于某一分支而非整个项目范围内的所有改动：

git pull origin specific-remote-branch-name

以上措施有助于保持本地开发环境相对隔离的状态，从而更灵活地管理不同版本间的差异[^3]。