T3-12 集合位置

思路解析

问题本质

从节点 1 到节点 n，求次短简单路径（不重复经过节点）。

关键观察

设最短路径为 P₁，次短路径为 P₂。由于 P₂ ≠ P₁，P₂ 必然至少缺少 P₁ 上的一条边。

算法：枚举删边

1. 先跑一次 Dijkstra，找到最短路径，记录路径上所有边
2. 依次删除最短路径上的每条边，每次重新跑 Dijkstra
3. 所有重跑结果中的最小值即为次短路径

正确性证明

• P₂ 不使用 P₁ 上的某条边 (u,v)
• 当我们删掉 (u,v) 后，Dijkstra 找到的最短路 ≤ P₂（因为 P₂ 仍然有效）
• 取所有删边方案的最小值，恰好就是次短路径

复杂度

• 最短路径最多 n-1 条边，每次删边跑 O(n²) 的 Dijkstra
• 总复杂度 O(n³)，对 n ≤ 200 绰绰有余

---

逐行注释代码

#include <iostream>                        // 引入输入输出流
#include <cstdio>                          // 引入 scanf/printf
#include <cmath>                           // 引入 sqrt 数学函数
using namespace std;

const int MAXN = 205;                      // 最大节点数
const double INF = 1e18;                   // 定义无穷大

int n, m;                                  // n: 节点数, m: 边数
double x[MAXN], y[MAXN];                   // 每个节点的坐标
double w[MAXN][MAXN];                      // 邻接矩阵，w[i][j] 为边权，-1 表示无边
double dist_arr[MAXN];                     // Dijkstra 中的最短距离数组
bool vis[MAXN];                            // Dijkstra 中的访问标记
int pre[MAXN];                             // 记录最短路径上每个节点的前驱

// 计算两点之间的欧几里得距离
double calc_dist(int a, int b) {
    double dx = x[a] - x[b];              // x 坐标之差
    double dy = y[a] - y[b];              // y 坐标之差
    return sqrt(dx * dx + dy * dy);        // 返回欧几里得距离
}

// Dijkstra 最短路，ban_u/ban_v 为本次禁用的边（-1 表示不禁用）
// need_pre 为是否需要记录前驱（只在第一次需要）
double dijkstra(int ban_u, int ban_v, bool need_pre) {
    for (int i = 1; i <= n; i++) {         // 初始化
        dist_arr[i] = INF;                // 所有距离设为无穷大
        vis[i] = false;                   // 所有节点标记为未访问
        if (need_pre) pre[i] = -1;        // 前驱初始化为 -1
    }
    dist_arr[1] = 0;                       // 起点距离为 0

    for (int iter = 0; iter < n; iter++) { // 最多进行 n 轮
        int u = -1;                        // 找未访问中距离最小的节点
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (u == -1 || dist_arr[j] < dist_arr[u]))
                u = j;                     // 更新最小距离节点
        }
        if (u == -1 || dist_arr[u] >= INF) // 没有可达节点了
            break;
        vis[u] = true;                     // 标记 u 为已访问

        for (int v = 1; v <= n; v++) {     // 枚举 u 的所有邻居
            if (vis[v]) continue;          // 已访问的跳过
            if (w[u][v] < 0) continue;     // 无边的跳过
            // 检查是否为被禁用的边（无向边，两个方向都要判）
            if ((u == ban_u && v == ban_v) || (u == ban_v && v == ban_u))
                continue;                 // 跳过被禁用的边
            if (dist_arr[u] + w[u][v] < dist_arr[v]) {  // 能松弛
                dist_arr[v] = dist_arr[u] + w[u][v];    // 更新最短距离
                if (need_pre) pre[v] = u;                // 记录前驱
            }
        }
    }
    return dist_arr[n];                    // 返回到终点 n 的最短距离
}

int main() {
    scanf("%d%d", &n, &m);                 // 读入节点数和边数

    for (int i = 1; i <= n; i++)           // 读入每个节点的坐标
        scanf("%lf%lf", &x[i], &y[i]);

    for (int i = 1; i <= n; i++)           // 初始化邻接矩阵
        for (int j = 1; j <= n; j++)
            w[i][j] = -1;                 // -1 表示无边

    for (int i = 0; i < m; i++) {          // 读入 m 条边
        int u, v;
        scanf("%d%d", &u, &v);
        if (u == v) continue;              // 自环没有意义，跳过
        double d = calc_dist(u, v);        // 计算这条边的欧几里得距离
        w[u][v] = d;                       // 无向图，存双向边
        w[v][u] = d;
    }

    // ========== 第一步：求最短路径 ==========
    double shortest = dijkstra(-1, -1, true);  // 不禁用任何边，记录前驱

    if (shortest >= INF) {                 // 起点到终点不连通
        printf("-1\n");                    // 连最短路都没有，更没有次短路
        return 0;
    }

    // ========== 第二步：记录最短路径上的边 ==========
    int path_u[MAXN], path_v[MAXN];        // 存储最短路径上的每条边
    int path_cnt = 0;                      // 最短路径的边数
    int cur = n;                           // 从终点开始回溯
    while (pre[cur] != -1) {               // 沿前驱链回溯到起点
        path_u[path_cnt] = pre[cur];       // 记录这条边的两个端点
        path_v[path_cnt] = cur;
        path_cnt++;                        // 边数 +1
        cur = pre[cur];                    // 移动到前驱
    }

    // ========== 第三步：枚举删边，求次短路 ==========
    double ans = INF;                      // 次短路初始为无穷大
    for (int i = 0; i < path_cnt; i++) {   // 遍历最短路径上的每条边
        // 删掉第 i 条边，重新跑 Dijkstra
        double res = dijkstra(path_u[i], path_v[i], false);
        if (res < ans)                     // 取所有方案中的最小值
            ans = res;
    }

    // ========== 第四步：输出结果 ==========
    if (ans >= INF)                        // 不存在次短路径
        printf("-1\n");
    else
        printf("%.2f\n", ans);             // 保留两位小数输出

    return 0;
}

---

注意事项

• 自环需要跳过（对最短路无贡献）
• 如果有多条最短路径，删掉其中一条的某条边后，另一条最短路径仍然存在，因此答案等于最短路径长度，符合题目要求