完整题面

一、前置知识

• 最短路算法（SPFA 或 Dijkstra）

二、题目大意

给定一个 $n$ 个点 $m$ 条边的无向图，求出从 $1$ 号点到 $n$ 号点的 次短路 长度

三、思考问题

对于复杂的问题，我们可以转换成熟悉的问题来思考

所以，求次短路的过程，可以转化成求次小值

那我们怎么求次小值呢？

• 在能更新最小值时，前一个最小值就是现在的次小值
• 不能更新最小值时，我们再考虑用当前值更新次小值

转换到图上，可以得到求次短路的方法：

• 在能更新最短路时，前一个最短路就是现在的次短路
• 不能更新最短路时，我们再考虑用当前路径长度更新次短路

四、代码实现

先写一个最短路模板（以 spfa 为例）

queue<int> q;
int dis1[5005], dis2[5005]; /* 最短路长度 与 次短路长度 */
bool vis[5005];

void spfa(int s, int t) {
    memset(dis1, 0x3f, sizeof(dis1));
    memset(vis, false, sizeof(vis));
    q.push(s);
    dis1[s] = 0;
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop(); vis[u] = false;

        for (int i = head[u]; i; i = Next[u]) {
            int v = ver[i];
            if (dis1[v] > dis1[u] + edge[i]) {
                dis1[v] = dis1[u] + edge[i];
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

我们在此基础上经行修改

考虑以下几个问题

1. 数组的初值

因为题目要求次短路为 长度最小的不等于最短路长度的路径 ，所以初始时次短路长度数组全都设为 $\inf$

2. 如何更新次短路

1. 用 下个点 的最短路更新

   if (dis1[v] > dis1[u] + edge[i]) {
       dis2[v] = dis1[v];
       dis1[v] = dis1[u] + edge[i];
   }
   

2. 用 当前点 的最短路更新

   if (dis1[v] < dis1[u] + edge[i] && dis2[v] > dis1[u] + edge[i]) {
       dis2[v] = dis1[u] + edge[i];
   }
   

3. 用 当前点 的次短路更新

   if (dis2[v] > dis2[u] + edge[i]) {
       dis2[v] = dis2[u] + edge[i];
   }
   

五、完整代码

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int n, m;

int tot, ver[200005], edge[200005], head[5005], Next[200005];
void add(int u, int v, int w) {
    ver[++tot] = v;
    edge[tot] = w;
    Next[tot] = head[u];
    head[u] = tot;
}

int dis1[5005], dis2[5005];
bool vis[5005];
queue<int> q;
void spfa(int s, int t) {
    memset(dis1, 0x3f, sizeof(dis1));
    memset(dis2, 0x3f, sizeof(dis2));
    memset(vis, false, sizeof(vis));
    q.push(s);
    vis[s] = true;
    dis1[s] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop(); vis[u] = false;

        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (dis1[v] > dis1[u] + edge[i]) {
                dis2[v] = dis1[v];
                dis1[v] = dis1[u] + edge[i];
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
            if (dis2[v] > dis1[u] + edge[i] && dis1[v] < dis1[u] + edge[i]) {
                dis2[v] = dis1[u] + edge[i];
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
            if (dis2[v] > dis2[u] + edge[i]) {
                dis2[v] = dis2[u] + edge[i];
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }

    spfa(1, n);

    printf("%d\n", dis2[n]);
    return 0;
}

提交看看

六、代码优化

1. 注意到图中没有负边权，所以将 SPFA 修改为 Dijkstra 效率会更高

2. 改用更直观的变量名

3. 添加注释

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_NODES = 5005;     // 最大节点数
const int MAX_EDGES = 200005;   // 最大边数（无向图需双倍存储）

int n, m;

// 邻接表存图结构
int edge_count;                  // 当前边数计数器
int to[MAX_EDGES];               // 边的终点
int weight[MAX_EDGES];           // 边权值
int next_edge[MAX_EDGES];        // 下一条边索引
int head[MAX_NODES];             // 每个节点的第一条边

// 添加无向边（正反各存一次）
void add_edge(int u, int v, int w) {
    to[++edge_count] = v;
    weight[edge_count] = w;
    next_edge[edge_count] = head[u];
    head[u] = edge_count;
}

int shortest[MAX_NODES];         // 最短距离数组
int second_shortest[MAX_NODES];  // 次短距离数组

void dijkstra(int start) {
    // 初始化距离为无穷大
    memset(shortest, 0x3f, sizeof(shortest));
    memset(second_shortest, 0x3f, sizeof(second_shortest));

    // 使用最小堆，存储 pair<当前距离, 节点编号>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> min_heap;

    shortest[start] = 0;
    min_heap.push({0, start});

    while (!min_heap.empty()) {
        auto current = min_heap.top();
        int current_dist = current.first;
        int u = current.second;
        min_heap.pop();

        // 如果当前路径长度已经大于记录的次短距离，跳过处理
        if (current_dist > second_shortest[u]) continue;

        // 遍历所有邻接边
        for (int edge_idx = head[u]; edge_idx; edge_idx = next_edge[edge_idx]) {
            int v = to[edge_idx];
            int edge_weight = weight[edge_idx];
            int new_distance = current_dist + edge_weight;

            /* 情况1：发现更短路径 */
            if (new_distance < shortest[v]) {
                // 原最短变为次短
                second_shortest[v] = shortest[v];  
                // 更新最短距离
                shortest[v] = new_distance;       
                // 两个新距离都需要加入堆
                min_heap.push({shortest[v], v});
                min_heap.push({second_shortest[v], v});
            }
            /* 情况2：发现更优次短路径（比最短长但比当前次短短） */
            else if (new_distance > shortest[v] && new_distance < second_shortest[v]) {
                second_shortest[v] = new_distance;
                min_heap.push({second_shortest[v], v});
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);

    // 构建无向图
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);  // 无向图双向添加
    }

    dijkstra(1);  // 从节点1出发

    printf("%d\n", second_shortest[n]);  // 输出到节点n的次短距离
    return 0;
}

建议、代码来源：deepseek（已验证代码正确性）

就好了