【例4-1】最短路径问题

形式化题目

给定平面上 $n$ 个点（ $n \leqslant 100$ ，坐标为 $-10000$ 到 $10000$ 的整数）和 $m$ 条连线。每条连线表示两端点之间可通行，通行长度等于两点的直线距离 $\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$ ，即把连线看成一个边权为欧氏距离的无向边。

求点 $s$ 到点 $t$ 之间的最短路径长度，保留两位小数输出。

解法总览

三种解法共用同一件事：建图——每条连线的边权就是两端点的欧氏距离。差别只在用哪种最短路算法。

	解法一：Floyd（正式主解）	解法二：SPFA（队列 Bellman-Ford）	解法三：堆优化 Dijkstra
存图方式	邻接矩阵 `dist[u][v]`	邻接表 `g[u]`	邻接表 `g[u]`
求什么	全源最短路	单源最短路（只求 $s$ ）	单源最短路（只求 $s$ ）
时间	$O(n^3)$	平均 $O(km)$ ，最坏 $O(nm)$	$O((n+m)\log n)$
边权要求	任意（无负环可达）	可带负权	非负
代码	`main.py` / `main.cpp`	`main-spfa.py` / `main-spfa.cpp`	`main-dijkstra.py` / `main-dijkstra.cpp`
适合场景	$n$ 小、还要随时查任意两点距离	带负权、稀疏图	非负权稀疏图，竞赛首选

本题 $n \leqslant 100$ 、只问一条路径，三种都能过。正式主解是 main.py / main.cpp（Floyd）：数据范围小，邻接矩阵三重循环最短，也最不容易写错。

解法一：Floyd（全源最短路）

思路

用邻接矩阵 d[u][v] 存图：d[i][i] = 0，有连线的两点之间存欧氏距离，其余先记成不可达的 $+\infty$ 。每条连线是无向边，所以 d[u][v] 和 d[v][u] 都要写。

然后跑 Floyd，把每个点 $k$ 轮流当中转点，用 d[i][k] + d[k][j] 去更新 d[i][j]。三重循环跑完，d[i][j] 就是任意两点的最短路，直接输出 d[s][t]。

注意中转点 $k$ 必须在最外层：这样用到 $k$ 时，前面 $k-1$ 个中转点已经处理好，d[i][k]、d[k][j] 都已是最终值。

浮点数的无穷大用 1e100 这种大数即可： $+\infty$ 加任何有限边权还是它自己，不会造出假的最短路。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-13 17:08
# update_at: 2026-10-13 17:08
#
# Floyd 全源最短路（邻接矩阵）：dist[i][j] 为 i 到 j 的最短路，INF 表示不可达。
# 点编号 1..n，坐标存 1 下标，dist[i][i] = 0，边权是两点间的欧氏距离；
# 本题只问 s 到 t，求完全源后取 dist[s][t] 输出。
# C++ 的 1e100 与 long long 在 Python 里是任意精度 int / float，不会溢出。

import sys
from math import hypot

INF = float("inf")  # 哨兵：inf 加任何有限边权仍是 inf，不会造出假最短路

type Grid = list[list[float]]
type Seq = list[float]


def build_dist(n: int, xs: Seq, ys: Seq, edges: list[tuple[int, int]]) -> Grid:
    """建邻接矩阵：dist[i][i] = 0，连线两端存欧氏距离，其余为 INF。"""
    dist: Grid = [[0.0 if i == j else INF for j in range(n + 1)] for i in range(n + 1)]
    for u, v in edges:
        w = hypot(xs[u] - xs[v], ys[u] - ys[v])  # 连线长度 = 两点间直线距离
        dist[u][v] = w
        dist[v][u] = w  # 连线是无向边，两个方向都登记
    return dist


def floyd(n: int, dist: Grid) -> Grid:
    """原地松弛：把 dist[i][j] 变成 i 到 j 的最短路长度。"""
    for k in range(1, n + 1):  # 中转点 k 必须在最外层，顺序不能换
        row_k = dist[k]
        for i in range(1, n + 1):
            i_to_k = dist[i][k]
            if i_to_k == INF:
                continue  # i 到中转点不可达，松弛无意义
            row_i = dist[i]
            for j in range(1, n + 1):
                if row_k[j] == INF:
                    continue
                whole = i_to_k + row_k[j]
                if whole < row_i[j]:
                    row_i[j] = whole
    return dist


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    xs: Seq = [0.0] * (n + 1)
    ys: Seq = [0.0] * (n + 1)
    for i in range(1, n + 1):  # 点的坐标，1 下标
        xs[i] = int(next(data))
        ys[i] = int(next(data))

    m = int(next(data))
    edges = [(int(next(data)), int(next(data))) for _ in range(m)]
    s, t = int(next(data)), int(next(data))

    dist = floyd(n, build_dist(n, xs, ys, edges))
    print(f"{dist[s][t]:.2f}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 10:47
 * update_at: 2026-10-05 10:47
 */

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 105;           // n <= 100
const double INF = 1e100;       // 不可达哨兵

int n, m, s, t;
double x[MAXN], y[MAXN];        // 点坐标
double d[MAXN][MAXN];           // 邻接矩阵，d[i][j] 表示 i 到 j 的最短距离

// 计算两点间欧氏距离，即连线的边权
double dist(int u, int v) {
    double dx = x[u] - x[v];
    double dy = y[u] - y[v];
    return sqrt(dx * dx + dy * dy);
}

// Floyd：原地松弛邻接矩阵，使 d[i][j] 成为任意两点最短路长度
void floyd() {
    for (int k = 1; k <= n; k++)          // 中转点放在最外层
        for (int i = 1; i <= n; i++)      // 起点
            for (int j = 1; j <= n; j++)  // 终点
                if (d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf %lf", &x[i], &y[i]);

    // 初始化邻接矩阵：自己到自己是 0，其余先记为不可达
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = (i == j) ? 0.0 : INF;

    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        double w = dist(u, v);
        d[u][v] = d[v][u] = w;  // 无向边，登记两个方向
    }

    scanf("%d %d", &s, &t);
    floyd();
    printf("%.2f\n", d[s][t]);
    return 0;
}

复杂度

时间： $O(n^3)$ ， $n = 100$ 时约 $10^6$ 次松弛。
空间： $O(n^2)$ 的邻接矩阵。

解法二：SPFA（单源最短路）

思路

本题只问 $s$ 到 $t$ 一条距离，用不着全源最短路，把 $s$ 作为源点做一次单源最短路就行。用链式前向星存图：每条无向连线拆成 $u \to v$ 和 $v \to u$ 两条有向边。

SPFA 是 Bellman-Ford 的队列实现，依据只有一条：只有被松弛过（距离变小）的点，才可能继续把别人放松。于是用队列维护"待松弛的点"：

dis[s] = 0，其余为 $+\infty$ ， $s$ 入队。
每次取出队首 $u$ ，扫它的整条边表，若 dis[u] + w < dis[v] 就更新 dis[v]，并把 $v$ 入队。
队列空时结束，dis[t] 就是答案。

in_queue[v] 防止同一个点重复入队。因为本题只问 $t$ ，dis[t] 之后再变小也不影响最终输出，所以简化的 SPFA 不需要判负环（欧氏距离恒为正，也不可能有负环）。

代码

Python 版（deque 队列 + 邻接表）：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-13 17:08
# update_at: 2026-10-13 17:08
#
# 邻接表 + SPFA 单源最短路：本题只问 s 到 t 一条距离，没必要做全源。
# 点编号 1..n，g[u] 存 u 的出边 (终点 v, 边权 w)，无向边两个方向各 append 一次；
# 边权是两点间欧氏距离，恒为正，所以不存在负环，不用判负环。
# C++ 的 long long 与 1e100 在这里是 Python int / float，任意精度，不会溢出。

import sys
from collections import deque
from math import hypot

INF = float("inf")  # 不可达哨兵

type WeightedAdj = list[list[tuple[int, float]]]
type Seq = list[float]


def spfa(n: int, g: WeightedAdj, source: int, target: int) -> float:
    """返回 source 到 target 的最短路；不可达返回 INF。"""
    dist: Seq = [INF] * (n + 1)
    in_queue = [False] * (n + 1)  # 标记点是否已在队列里，避免重复入队
    dist[source] = 0

    q: deque[int] = deque([source])
    in_queue[source] = True
    while q:
        u = q.popleft()
        in_queue[u] = False  # 出队后允许再次入队（之后可能被松弛得更小）

        for v, w in g[u]:
            whole = dist[u] + w
            if whole < dist[v]:  # 只有被松弛过的点才可能继续松弛别人
                dist[v] = whole
                if not in_queue[v]:
                    q.append(v)
                    in_queue[v] = True

    return dist[target]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    xs: Seq = [0.0] * (n + 1)
    ys: Seq = [0.0] * (n + 1)
    for i in range(1, n + 1):  # 点的坐标，1 下标
        xs[i] = int(next(data))
        ys[i] = int(next(data))

    m = int(next(data))
    g: WeightedAdj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = int(next(data)), int(next(data))
        w = hypot(xs[u] - xs[v], ys[u] - ys[v])  # 连线长度 = 两点间直线距离
        g[u].append((v, w))
        g[v].append((u, w))  # 无向边：两个方向各存一次
    s, t = int(next(data)), int(next(data))

    print(f"{spfa(n, g, s, t):.2f}")


if __name__ == "__main__":
    solve()

C++ 版（链式前向星 + 同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-13 16:31
 * update_at: 2026-10-13 16:31
 */
// main-spfa.cpp：链式前向星存图 + SPFA 求单源最短路。
// 和 main.cpp（Floyd 全源最短路）解同一道题：本题只问 s 到 t 一条距离，
// 单源算法比全源更省（Floyd 要 O(n^3)，SPFA 平均 O(k*m)）；n ≤ 100 时两者都能过。

#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;

typedef long long ll;

const int maxn = 105;      // 点数上界：n ≤ 100
const int maxm = maxn * maxn; // 连线数上界：最多 maxn 个点两两连线
const double INF = 1e100;  // 不可达哨兵：加任何有限边权后仍是它自己，不会造出假最短路

int n, m, s, t;
double px[maxn], py[maxn]; // 每个点的坐标

// 链式前向星：一条有向边记终点、权值、同起点的下一条边
struct Edge {
    int to;
    double w;
    int nxt; // 同一起点边表中的下一条边，0 表示没有了
};
Edge edge[2 * maxm]; // 每条连线是无向边，拆成两条有向边，所以开两倍
int head[maxn];      // head[u] 是 u 的边表头，0 表示空表；-1 表示没放过边
int edge_cnt;        // 已加入的边数，add_edge 用它开新边

// 加一条有向边 u -> v，边权 w
void add_edge(int u, int v, double w) {
    edge_cnt++;
    edge[edge_cnt].to = v;
    edge[edge_cnt].w = w;
    edge[edge_cnt].nxt = head[u];
    head[u] = edge_cnt;
}

// 两点间直线距离，也就是这条连线的边权
double dist(int u, int v) {
    double dx = px[u] - px[v];
    double dy = py[u] - py[v];
    return sqrt(dx * dx + dy * dy);
}

// SPFA：只有被松弛过的点才可能继续松弛别人，用队列存这些点
double spfa() {
    double dis[maxn];  // dis[i] 是当前从 s 到 i 的最短距离
    int in_queue[maxn]; // in_queue[i] 表示 i 是否正在队列里，避免重复入队

    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        in_queue[i] = 0;
    }
    dis[s] = 0;

    queue<int> q;
    q.push(s);
    in_queue[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = 0;

        // 扫 u 的整条边表，尝试用 u 松弛每个邻居 v
        for (int e = head[u]; e != 0; e = edge[e].nxt) {
            int v = edge[e].to;
            double nd = dis[u] + edge[e].w;
            if (nd < dis[v]) {
                dis[v] = nd;
                if (!in_queue[v]) { // 队列里已经有 v 就不用重复放
                    q.push(v);
                    in_queue[v] = 1;
                }
            }
        }
    }
    return dis[t];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf %lf", &px[i], &py[i]);

    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        double w = dist(u, v);
        add_edge(u, v, w); // 无向边：两个方向各加一条
        add_edge(v, u, w);
    }

    scanf("%d %d", &s, &t);
    printf("%.2f\n", spfa());
    return 0;
}

复杂度

时间：平均 $O(km)$ （ $k$ 是每个点平均入队次数，通常不超过常数），最坏 $O(nm)$ 。
空间： $O(n + m)$ ，链式前向星的结构数组。

解法三：堆优化 Dijkstra（单源最短路）

思路

同样是单源最短路，但换一条正确性依据：本题边权是欧氏距离，恒为非负，所以每个点一旦作为当前距离最小的点出堆，它的最短路就确定了，之后不会再被改小。这就是 Dijkstra。

用小根堆（priority_queue + greater）保存 (距离, 点编号)，保证每次取出的是未确定点里距离最小的：

dis[s] = 0，(0, s) 入堆。
弹出堆顶点 $u$ ；若 done[u] 已经为真说明这是同一个点的旧记录，直接跳过（点被松弛一次就入堆一次，堆里允许有重复）。
否则标记 done[u] = 1，用 $u$ 松弛它的所有邻居并把更新过的邻居入堆。
因为只问 $s$ 到 $t$ ，u == t 时可以直接 break。

非负权是硬前提：边权为负时，“出堆即定” 不成立，必须改用 SPFA 或 Bellman-Ford。

代码

Python 版（heapq 小根堆 + 邻接表）：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-13 17:08
# update_at: 2026-10-13 17:08
#
# 邻接表 + 堆优化 Dijkstra 单源最短路：本题只问 s 到 t 一条距离。
# 点编号 1..n，g[u] 存 u 的出边 (终点 v, 边权 w)，无向边两个方向各存一次。
# 边权是两点间欧氏距离，恒为非负，所以每个点出堆时它的最短路已确定，不会再变。
# C++ 的 long long 与 1e100 在这里是 Python int / float，任意精度，不会溢出。

import sys
from heapq import heappop, heappush
from math import hypot

INF = float("inf")  # 不可达哨兵

type WeightedAdj = list[list[tuple[int, float]]]
type Seq = list[float]


def dijkstra(n: int, g: WeightedAdj, source: int, target: int) -> float:
    """返回 source 到 target 的最短路；不可达返回 INF。"""
    dist: Seq = [INF] * (n + 1)
    done = [False] * (n + 1)  # done[u] 为真表示 u 已出堆，最短路已确定
    dist[source] = 0

    # 小根堆放 (当前距离, 点编号)，保证每次取出未确定点里距离最小的那个
    pq: list[tuple[float, int]] = [(0.0, source)]
    while pq:
        d, u = heappop(pq)
        if done[u]:
            continue  # 同一个点可能进堆多次，只有第一次有用
        done[u] = True
        if u == target:
            break  # 只问 s 到 t，t 确定了就可以停

        for v, w in g[u]:
            whole = d + w
            if whole < dist[v]:
                dist[v] = whole
                heappush(pq, (whole, v))  # 旧的 (dist, v) 留在堆里，靠 done 跳过

    return dist[target]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    xs: Seq = [0.0] * (n + 1)
    ys: Seq = [0.0] * (n + 1)
    for i in range(1, n + 1):  # 点的坐标，1 下标
        xs[i] = int(next(data))
        ys[i] = int(next(data))

    m = int(next(data))
    g: WeightedAdj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = int(next(data)), int(next(data))
        w = hypot(xs[u] - xs[v], ys[u] - ys[v])  # 连线长度 = 两点间直线距离
        g[u].append((v, w))
        g[v].append((u, w))  # 无向边：两个方向各存一次
    s, t = int(next(data)), int(next(data))

    print(f"{dijkstra(n, g, s, t):.2f}")


if __name__ == "__main__":
    solve()

C++ 版（链式前向星 + 同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-13 16:31
 * update_at: 2026-10-13 16:31
 */
// main-dijkstra.cpp：链式前向星存图 + 二叉堆优化 Dijkstra 求单源最短路。
// 和 main-spfa.cpp 同为单源解法，区别在正确性依据：本题边权是欧氏距离，
// 恒为非负，所以可以用 Dijkstra——每个点出堆时它的最短路已经确定，不再更新。

#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;

const int maxn = 105;      // 点数上界：n ≤ 100
const int maxm = maxn * maxn; // 连线数上界：最多 maxn 个点两两连线
const double INF = 1e100;  // 不可达哨兵

int n, m, s, t;
double px[maxn], py[maxn]; // 每个点的坐标

// 链式前向星：一条有向边记终点、权值、同起点的下一条边
struct Edge {
    int to;
    double w;
    int nxt; // 同一起点边表中的下一条边，0 表示没有了
};
Edge edge[2 * maxm]; // 无向边拆两条有向边
int head[maxn];      // head[u] 是 u 的边表头，0 表示空表
int edge_cnt;        // 已加入的边数

// 加一条有向边 u -> v，边权 w
void add_edge(int u, int v, double w) {
    edge_cnt++;
    edge[edge_cnt].to = v;
    edge[edge_cnt].w = w;
    edge[edge_cnt].nxt = head[u];
    head[u] = edge_cnt;
}

// 两点间直线距离，也就是这条连线的边权
double dist(int u, int v) {
    double dx = px[u] - px[v];
    double dy = py[u] - py[v];
    return sqrt(dx * dx + dy * dy);
}

// 小根堆的元素：first 是当前距离，second 是点编号；
// greater 让距离小的先出堆，first 相同时比较编号，不影响结果
typedef pair<double, int> Node;

// 堆优化 Dijkstra：每次取出当前距离最小的点，用它松弛邻居
double dijkstra() {
    double dis[maxn]; // dis[i] 是当前从 s 到 i 的最短距离
    int done[maxn];   // done[i] = 1 表示 i 已经出堆，最短路已确定

    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        done[i] = 0;
    }
    dis[s] = 0;

    priority_queue<Node, vector<Node>, greater<Node> > heap;
    heap.push(make_pair(0.0, s));
    while (!heap.empty()) {
        int u = heap.top().second; // 堆顶是还没确定的点里距离最小的
        heap.pop();
        if (done[u]) continue; // 同一个点可能进堆多次，只有第一次有用
        done[u] = 1;
        if (u == t) break;     // 只问 s 到 t，t 确定了就可以停

        // 扫 u 的整条边表，尝试用 u 松弛每个邻居 v
        for (int e = head[u]; e != 0; e = edge[e].nxt) {
            int v = edge[e].to;
            double nd = dis[u] + edge[e].w;
            if (nd < dis[v]) {
                dis[v] = nd;
                heap.push(make_pair(nd, v)); // 旧的 (dis, v) 留在堆里，靠 done 跳过
            }
        }
    }
    return dis[t];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf %lf", &px[i], &py[i]);

    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        double w = dist(u, v);
        add_edge(u, v, w); // 无向边：两个方向各加一条
        add_edge(v, u, w);
    }

    scanf("%d %d", &s, &t);
    printf("%.2f\n", dijkstra());
    return 0;
}

复杂度

时间： $O((n+m)\log n)$ ，每条边最多带来一次入堆。
空间： $O(n + m)$ 。

复杂度对比

解法	时间	空间	关键前提
Floyd	$O(n^3)$	$O(n^2)$	无（只求可达的最短路）
SPFA	平均 $O(km)$ ，最坏 $O(nm)$	$O(n+m)$	边权可负，不能有负环
堆优化 Dijkstra	$O((n+m)\log n)$	$O(n+m)$	边权非负

选择依据看两点：要不要全源、边权会不会为负。本题 $n \leqslant 100$ 且只问一条路径，三者都能过；数据范围一旦变大，就该从 Floyd 换成 Dijkstra 或 SPFA。

总结

本题的建图环节才是题目的主要信息量：连线 = 无向边，边权 = 欧氏距离；把这步想清楚，剩下就是套最短路模板。
$n \leqslant 100$ 时 Floyd 的 $O(n^3)$ 完全够用，而且顺带得到全源最短路；只有数据变大或只问单源时才需要换算法。
单源最短路的存图选择看需求：Python 日常用邻接表 g[u].append((v, w)) 最直观，C++ 需要边编号或反向边时用链式前向星（add_edge 加有向边，无向边加两次，head[] 是边表头，nxt 串起同起点的边）。
三种算法的适用边界要记牢：Dijkstra 要求边权非负，SPFA/Bellman-Ford 可以带负权但最坏更慢，Floyd 无所谓边权但代价是 $O(n^3)$ 。
浮点数最短路注意两点：无穷大用足够大的有限数（如 1e100），输出按题目要求 .2f 四舍五入。