luogu P2865 路障

https://www.luogu.org/problemnew/show/P2865

看到题解好多dijkstra，作为一名钟爱于spfa的蒟蒻看不下去了。

有些spfa要跑两边，代码量要曾长好多(虽然复制)，而且还慢。

下面开始我的表演：

首先看清楚题意：题目说的是从n点往回走(因为双向边，所以好多人注意到也过了)

接着明确一个数组：

d[i][0]表示到i点的最短路

d[i][1]表示到i点的次短路

初始化数组，d[n][0]=0,d[n][1]=INF,其他的也都是INF；

然后将点进入队列开始，进行对其他点的更改。

记当前节点编号为u，目前所连边的编号为v。

我们将判断分为两块

(1)d[u][0]对于v点的影响。

(2)d[u][1]对于v点的影响。

#### (1)

如果$$d[u][0]+dis[u,v]<d[v][0]$$,也就是说足影响v点，那么此时的次短路变成了更新前的最短路，最短路更新。

如果
$$d[v][0]<=d[u][0]+dis[u,v]$$

$$d[v][0]>=d[u][0]+dis[u,v]$$

就是说不足以影响最短路，却可以影响次短路，能更新自然更新。

#### (2)

再开始判断d[u][1]对v点的影响

前边(1)部分先更新的最短路。

如果足矣更新最短路：那么到u点的最短路一定小于到u点的次短路，所以用d[u][0]一定更优。

如果没有更新：那么既然最短路都不能更新了，次短路还有啥用。

总的来说对v点最短路这一块理解就好，木有代码。

对于次短路我们要判断一下是否更新。

注意注意：以上判断都需要注意次短路严格小于最短路。

所以：

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <stack>

#include <queue>

using namespace std;

struct ahah{

    int nxt,to,dis;

}edge[];

int n,m;

int head[],tot;

void add(int x,int y,int z)

{

    edge[++tot].nxt=head[x],edge[tot].to=y,edge[tot].dis=z,head[x]=tot;

}

int d[][];

bool vis[];

queue <int> que;

int read()

{

    int sum=,fg=; char c=getchar();

    while(c<''||c>''){if(c=='-')fg=-;c=getchar();}

    while(c>=''&&c<=''){sum=sum*+c-'';c=getchar();}

    return sum*fg;

}

void spfa(int s)

{

    memset(d,0x7f,sizeof(d));

    que.push(s);vis[s]=;

    d[s][]=;

    while(!que.empty())

    {

        int u=que.front();

        vis[u]=;que.pop() ;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int v=edge[i].to;

            if(d[v][]>d[u][]+edge[i].dis)

            {

                d[v][]=d[v][];

                d[v][]=d[u][]+edge[i].dis;

                if(!vis[v])vis[v]=,que.push(v);

            }

            if(d[v][]>d[u][]+edge[i].dis&&d[u][]+edge[i].dis>d[v][])

            {

                d[v][]=d[u][]+edge[i].dis;

                if(!vis[v])vis[v]=,que.push(v);

            }

            if(d[v][]>d[u][]+edge[i].dis)

            {

                d[v][]=d[u][]+edge[i].dis;

                if(!vis[v])vis[v]=,que.push(v);

            }

        }

    }

}

int main()

{

    int x,y,z;

    n=read();m=read();

    for(int i=;i<=m;i++)

    {

        x=read(),y=read(),z=read();

        add(x,y,z);add(y,x,z);

    }

    spfa(n);

    printf("%d",d[][]);

}

巴特西

luogu P2865 路障

最新文章

热门文章