[Acwing] 道路与航线 负权最短路

前言

处理负权 传送门 :

思路

因为有负权 所以我们无法使用 dij

因此我们考虑 s p f a spfa spfa 但是这题 中 等 中等 中等 不是盖的

所以我们需要优化

SLF 我们可以采用双端队列优化

每次对于 d i s t [ x . t o ] > d i s t [ t ] + x . v a l dist[x.to]>dist[t]+x.val dist[x.to]>dist[t]+x.val

• 如果当前的点 小于 队头 那么我们让他加入队头

• 如果当前的点 大于 队头 那么我们让他加入队尾

CODE

#include 
using namespace std;
const int N = 3e4+10;
int n,r,p,s;
int dist[N],st[N];

struct Edge
{
    int to,val;
};

vector g[N];
void spfa(int s)
{
    memset(dist,0x3f,sizeof dist);
    deque q;
    dist[s] = 0;
    st[s]  =1;

    q.push_back(s);
    while(!q.empty())
    {

        //coutr>>p>>s;
    while(r -- )
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }

    while(p -- )
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a].push_back({b,c});
    }

    spfa(s);
    for(int i=1;i