思路总览

核心想法

把“索道”视为一条权值为 0 的无向边 (A, B)。 用 Floyd-Warshall 求全源最短路，直接得到所有点对最短距离。最终答案就是 dist[s][e]。

复杂度

• 时间：O(n^3)（n ≤ 100，可承受）
• 空间：O(n^2)

Python 代码

import sys

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    it = iter(data)
    n = next(it); m = next(it)
    s = next(it); e = next(it)
    A = next(it); B = next(it)

    INF = 10**15
    d = [[INF]*(n+1) for _ in range(n+1)]
    for i in range(1, n+1):
        d[i][i] = 0

    # 读边，构建无向图
    for _ in range(m):
        u = next(it); v = next(it); w = next(it)
        if w < d[u][v]:
            d[u][v] = d[v][u] = w

    # 加入 0 费用索道
    d[A][B] = d[B][A] = 0

    # Floyd
    for k in range(1, n+1):
        dk = d[k]
        for i in range(1, n+1):
            dik = d[i][k]
            if dik == INF: 
                continue
            di = d[i]
            for j in range(1, n+1):
                v = dik + dk[j]
                if v < di[j]:
                    di[j] = v

    print(d[s][e])

if __name__ == "__main__":
    main()

Java 代码

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String line;
        while ((line = br.readLine()) != null) {
            line = line.trim();
            if (line.length() == 0) continue;
            sb.append(line).append(' ');
        }
        String[] tok = sb.toString().trim().split("\\s+");
        int idx = 0;

        int n = Integer.parseInt(tok[idx++]);
        int m = Integer.parseInt(tok[idx++]);
        int s = Integer.parseInt(tok[idx++]);
        int e = Integer.parseInt(tok[idx++]);
        int A = Integer.parseInt(tok[idx++]);
        int B = Integer.parseInt(tok[idx++]);

        long INF = (long)1e15;
        long[][] d = new long[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(d[i], INF);
            d[i][i] = 0;
        }

        // 读入边，更新无向最小权
        for (int i = 0; i < m; i++) {
            int u = Integer.parseInt(tok[idx++]);
            int v = Integer.parseInt(tok[idx++]);
            int w = Integer.parseInt(tok[idx++]);
            if (w < d[u][v]) {
                d[u][v] = w;
                d[v][u] = w;
            }
        }

        // 加入 0 费用索道
        d[A][B] = 0;
        d[B][A] = 0;

        // Floyd
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                if (d[i][k] == INF) continue;
                for (int j = 1; j <= n; j++) {
                    long v = d[i][k] + d[k][j];
                    if (v < d[i][j]) d[i][j] = v;
                }
            }
        }

        System.out.println(d[s][e]);
    }
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if(!(cin >> n >> m)) return 0;
    int s, e, A, B;
    cin >> s >> e >> A >> B;

    const long long INF = (long long)1e15;
    vector<vector<long long>> d(n+1, vector<long long>(n+1, INF));
    for(int i=1;i<=n;i++) d[i][i]=0;

    for(int i=0;i<m;i++){
        int u,v,w; cin >> u >> v >> w;
        if(w < d[u][v]){
            d[u][v] = w;
            d[v][u] = w; // 无向边
        }
    }

    // 索道 0 费用
    d[A][B] = d[B][A] = 0;

    // Floyd
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            if(d[i][k]==INF) continue;
            for(int j=1;j<=n;j++){
                long long v = d[i][k] + d[k][j];
                if(v < d[i][j]) d[i][j] = v;
            }
        }
    }

    cout << d[s][e] << "\n";
    return 0;
}

题目内容

某定向越野赛事在一片山区举行，山区内共有$n$个打卡点(编号为$1$ ~$n$)，打卡点之间有$m$条可供通行的山 路，每条山路通行都要花费固定的通行时间(单位:分钟)。赛事要求选手从“起点打卡点”出发，最终到达 “终点打卡点”。 组委会在某两个打卡点$A$和$B$之间设置了一条特殊索道，选手可以通过该索道在这两个打卡点之间瞬间往返 (不消耗时间). 请计算选手从起点到终点的最短通行时间(保证存在可达路径)。

输入描述

第一行两个正整数$n,m$，分别表示打卡点总数和山路数量

第二行两个正整数，分别表示“起点打卡点”和“终点打卡点”的编号。

第三行两个正整数，分别表示设有特殊索道的两个打卡点的编号。

接下来$m$ 行，每行三个正整数$u,v,t$，分别表示打卡点 $u$和$v$之间有一条山路，双向通行，通过该山 路需要消耗$t$分钟。

$1 <= n <= 100, 1 <= m <= 2* n$，每条道路的时间花费在$[1,10]$之间。

输出描述

一个整数表示最短通行时间。

样例1

输入

6 5
2 6 
3 5
2 3 3
3 4 2
4 5 1
5 6 4
2 4 5

输出

7