次短路径问题题解

一、题目分析

贝茜需要从路口1到路口N，求次短路径长度。次短路径定义为：所有比最短路径长的路径中最短的一条。关键条件：

• 路径可以重复经过道路或路口；
• 次短路径长度必须严格大于最短路径。

二、算法思路

1. 最短路径预处理：分别以起点1和终点N为源点，计算各点到源点的最短路径d[]和d1[]（d[u]为1到u的最短距离，d1[v]为N到v的最短距离）。
2. 次短路径求解：枚举所有边(u, v, w)，计算d[u] + w + d1[v]，该值表示从1到u，经边(u,v)，再从v到N的路径长度。所有合法值（>最短路径）中的最小值即为次短路径。

三、代码实现

/*
次短路求解方法：若要求a到b的次短路,先以a为起点进行一次spfa,得到的数组为d,再以b为
起点进行spfa,得到数组为d1,然后枚举所给的每一条直连边,假设端点为u,v,边长为w,
求得每一个d[u]+d1[v]+w,取这些中大于最短路的最小的一个就是次短路. 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 5000 + 10;
const int maxm = 200000 + 10;
const int inf = 0x3f3f3f3f;

int d[maxn], d1[maxn], head[maxn], inq[maxn], q[maxn];
int tol = 0;
int n, r;

struct Edge {
    int from, to, w, next;
} edge[maxm];

void init() {
    memset(head, -1, sizeof(head));
    tol = 0;
}

void addedge(int u, int v, int w) {
    edge[tol].from = u, edge[tol].to = v, edge[tol].w = w, edge[tol].next = head[u], head[u] = tol++;
    edge[tol].from = v, edge[tol].to = u, edge[tol].w = w, edge[tol].next = head[v], head[v] = tol++;
}

void spfa(int s, int *d) {
    memset(inq, 0, sizeof(inq));
    memset(q, 0, sizeof(q));
    for (int i = 1; i <= n; i++) d[i] = inf;
    d[s] = 0, inq[s] = 1;
    int front = 0, rear = 0;
    q[rear++] = s;
    while (front != rear) {
        int u = q[front++];
        inq[u] = 0;
        if (front >= maxn) front = 0;
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to, w = edge[i].w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                if (inq[v]) continue;
                inq[v] = 1;
                q[rear++] = v;
                if (rear >= maxn) rear = 0;
            }
        }
    }
}

int main() {
    while (~scanf("%d%d", &n, &r)) {
        init();
        while (r--) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
        }
        spfa(1, d);
        spfa(n, d1);
        int ans = d[n], res = inf;
        for (int i = 0; i < tol; i++) {
            int u = edge[i].from, v = edge[i].to, w = edge[i].w;
            if (d[u] + d1[v] + w > ans)
                res = min(res, d[u] + d1[v] + w);
        }
        printf("%d\n", res);
    }
}

四、代码解释

1. 图的构建：
   • 使用邻接表存储无向图，addedge函数添加双向边。
2. 最短路径计算：
   • spfa算法计算单源最短路径：spfa(1, d)求1到各点的最短路径d[]；spfa(n, d1)求N到各点的最短路径d1[]。
3. 次短路径求解：
   • 枚举所有边(u, v, w)，计算路径1→u→v→N的长度d[u] + w + d1[v]。
   • 筛选出所有大于最短路径ans = d[n]的值，取最小值作为次短路径。

五、示例解析

输入样例：

4 4  
1 2 100  
2 4 200  
2 3 250  
3 4 100  

1. 最短路径计算：
   • 1→2→4的长度为100+200=300，是1到4的最短路径ans=300。
2. 枚举边计算次短路径：
   • 边(2,3,250)：d[2]=100，d1[3]=100（3→4的最短路径为100），路径长度100+250+100=450。
   • 其他边的计算结果均≥450，故次短路径为450。

六、复杂度分析

• 时间复杂度：
  • 两次SPFA：O(R)（均摊时间，适用于稀疏图）；
  • 枚举边：O(R)。
  • 总复杂度：O(R)，适用于R≤10⁵的数据规模。
• 空间复杂度：O(N+R)，邻接表存储图的空间。

七、核心思想

利用最短路径的性质，通过枚举所有边构造可能的次短路径。该方法避免了显式枚举所有路径，而是通过最短路径预处理和边枚举高效求解，是次短路径问题的经典解法之一。