题目描述

Description

有n个点 m条无向边 求出从1到n的(严格)次短路径长度

题目分析

求次短路 用 SPFA AC 而且一个点只要被更新 不管是最短路还是次短路被更新 都要将它压入队列

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int head[200100];
int next[200100];
int to[200100];
int val[200100];
int tot;
int dis[200100][2];
void add(int x,int y,int c)
{
    next[++tot]=head[x];
    to[tot]=y;
    val[tot]=c;
    head[x]=tot;
}
bool vis[200100];
queue<int>q;
void spfa(int x)
{
    memset(dis,0x3f,sizeof dis);
    dis[x][1]=0;
    q.push(x);
    while(q.size())
    {
        int nmp=q.front();
        q.pop();
        for(int i=head[nmp];i;i=next[i])
        {
            int tmp=dis[nmp][1]+val[i];
            if(dis[to[i]][1]>tmp)
            {
                dis[to[i]][2]=dis[to[i]][1];
                dis[to[i]][1]=tmp;
                q.push(to[i]);
                continue;
            }
            else if(dis[to[i]][2]>tmp&&dis[to[i]][1]<tmp)
            {
                dis[to[i]][2]=tmp;
                q.push(to[i]);
                continue;
            }
            else if(dis[to[i]][2]>dis[nmp][2]+val[i]&&dis[to[i]][1]<dis[nmp][2]+val[i])
            {
                dis[to[i]][2]=dis[nmp][2]+val[i];
                q.push(to[i]);
            }
        }
    }

}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        add(x,y,c);
        add(y,x,c);
    }
    spfa(1);
    printf("%d",dis[n][2]);
    return 0;
}