题目描述：

给你n个点，m条边。问你从1号点到n号点的次短路是多少。

解题报告：

用d[0][i]表示1点到i点的最短路（一遍spfa）

用d[1][i]表示n点到i点的最短路（一遍spfa）

遍历所有边：

如果d[0][边起点] + 边权 + d[1][边终点]不等于d[0][n]，所有的这些的最小值就是答案。

同理，可以应用到k短路，都是这样找就可以。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define size 5001
struct edge{int from, to, val, next;} e[300000];
int que[size * 10], v[size], n, cnt, m, d[2][size]; bool vst[size];
void insert(int from, int to, int val)
{
    e[cnt].from = from, e[cnt].to = to, e[cnt].val = val;
    e[cnt].next = v[from]; v[from] = cnt++;
}
void spfa(int sta, int n, int *d)
{
    memset(vst, 0, sizeof(bool) * (n + 1));
    memset(d, -1, sizeof(int) * (n + 1));
    int head = 0, tail = 0;
    que[tail++] = sta; vst[sta] = 1; d[sta] = 0;
    while(head < tail)
    {
        vst[que[head++]] = 0;
        for(int i = v[que[head - 1]]; i != -1; i = e[i].next)
            if (d[e[i].to] == -1 || d[e[i].from] + e[i].val < d[e[i].to])
            {
                d[e[i].to] = d[e[i].from] + e[i].val;
                if (!vst[e[i].to]) vst[e[i].to] = 1, que[tail++] = e[i].to;
            }
    }
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(v, -1, sizeof(int) * (n + 1)); cnt = 0;
        while(m--)
        {
            int a, b ,c;scanf("%d%d%d", &a, &b, &c);
            insert(a, b, c); insert(b, a, c);
        }
        spfa(1, n, d[0]), spfa(n, n, d[1]);
        int ans = 0x7fffffff;
        for(int i = 0; i < cnt; i++)
            if (d[0][e[i].from] != -1 && d[1][e[i].to] != -1 && d[0][e[i].from] + d[1][e[i].to] + e[i].val != d[0][n])
                ans = min(ans, d[0][e[i].from] + d[1][e[i].to] + e[i].val);
        printf("%d\n", ans);
    }
    return 0;
}