A*算法 -> bfs

K短路

spfa

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5010, M = 200010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dis[N][2];
bool st[N];
int q[N];

void add (int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa ()
{
    memset(dis, 0x3f, sizeof dis);
    dis[1][0] = 0;

    int hh = 0, tt = 1;
    q[0] = 1;

    while(hh != tt)
    {
        int t = q[hh ++ ];
        if(hh == N) hh = 0;
        st[t] = 0;

        for(int i = h[t] ; ~i ; i = ne[i])
        {
            int j = e[i];

            if(dis[j][0] > dis[t][0] + w[i]) // 最短路更新
            {
                dis[j][1] = dis[j][0];
                dis[j][0] = dis[t][0] + w[i];

                if(!st[j])
                {
                    st[j] = 1;
                    q[tt ++ ] = j;
                    if(tt == N) tt = 0;
                }
            }
            if(dis[j][1] > dis[t][1] + w[i]) // 次短路更新
            {
                dis[j][1] = dis[t][1] + w[i];
                if(!st[j])
                {
                    st[j] = 1;
                    q[tt ++ ] = j;
                    if(tt == N) tt = 0;
                }
            }
            if(dis[j][0] < dis[t][0] + w[i] && dis[j][1] > dis[t][0] + w[i])
            {
                dis[j][1] = dis[t][0] + w[i];
                if(!st[j])
                {
                    st[j] = 1;
                    q[tt ++ ] = j;
                    if(tt == N) tt = 0;
                }
            }
        }
    }
}

int main ()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);
    for(int i = 0 ; i < m ; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;

        add(a, b, c), add(b, a, c);
    }

    spfa();

    cout << dis[n][1] << endl;

    return 0;
}

dij_heap

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 5010, M = 200010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dis[N][2];
int st[N][2];

struct loc 
{
    int id, type, d;
    bool operator > (const loc &b) const
    {
        return d > b.d;
    }
};

void add (int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dij_heap ()
{
    memset(dis, 0x3f, sizeof dis);
    dis[1][0] = 0;

    priority_queue<loc, vector<loc>, greater<loc>> pq;
    pq.push({1, 0, 0});

    while(pq.size())
    {
        auto t = pq.top();
        pq.pop();

        int ver = t.id, type = t.type, distance = t.d;

        if(st[ver][type]) continue;
        st[ver][type] = 1;

        for(int i = h[ver] ; ~i ; i = ne[i])
        {
            int j = e[i];

            if(dis[j][0] > distance + w[i])
            {
                dis[j][1] = dis[j][0];
                dis[j][0] = distance + w[i];
                pq.push({j, 0, dis[j][0]});
                pq.push({j, 1, dis[j][1]});
            }
            if(dis[j][0] < distance + w[i] && dis[j][1] > distance + w[i])
            {
                dis[j][1] = distance + w[i];
                pq.push({j, 1, dis[j][1]});
            }
        }
    }
}

int main ()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);
    for(int i = 0 ; i < m ; i ++ )
    {
        int a, b, c;
        cin >> a >>b >> c;

        add(a, b, c), add(b, a, c);
    }

    dij_heap();

    cout << dis[n][1] << endl;

    return 0;
}

板子题 第二短路
参考资料