每日一题 wpy的请求 (spfa)

一.题意

给出 n 个点和 m条边的有向图，边权可能为负值，修改任意边权，使所有边权非负且任意<u,v>的最短路路径不变。

二.题解

关键点在于两个：

建图。最短路+负边权不难联想到 $spfa$ ，由于是单源最短路，所以要增加一个超级源点，保证原本的 n 个点都有对应的最短路。
边权。最短路松弛条件为 $d[v] > d[u] + w$ ，松弛形式为 $d[v] = d[u] + w$ ，所以跑完 $spfa$ 后肯定成立的有对于任意 $<u,v>$ : $d[u] + w - d[v] >= 0(这里大于的原因是可能当前d[v]可能不是由d[u]更新的)$ 。

参考官方题解的证明:
以超级源点存在为前提，对于最短路 $u -> x->v$ ，有：

$dis = w(u,x) + w(x,v)$

保证所有的最短路方案都不变，我们考虑使得新的最短只与旧最短路以及起点终点有关，与其他的值都无关，
所以我们只需要在在最短路松弛中消去其他的值，考虑对于任意边 $<a,b>$ ，令其边权为 $d[a] + w - d[b]$
(上面已经证得为非负数)，就可以保证对每条最短路的影响只与 $d[u]和d[v]$ 有关。
对于原最短路 $u -> x->v$ ，有：

$(d[u] + w(u,x) -d[x]) +(d[x]+ w(x,v)-d[v]) = dis + (d[u] - d[v])$

三.代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define eps 1e-10
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e5+5;
const int N=5e3+5;
const int mod=1e9+7;

ll head[N],d[N];
bool vis[N];
struct node{
    ll next,v,w,u;
}a[manx];
ll n,m,s,e,k;
void add(ll u,ll v,ll w){
    a[++k].v=v; a[k].u=u; a[k].next=head[u]; a[k].w=w; head[u]=k;
}
void spfa(){
    queue<ll>q;
    for(int i=0;i<=n;i++) d[i]=inf,vis[i]=0;
    q.push(s); vis[s]=1; d[s]=0;
    while(q.size()){
        ll u=q.front(); q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=a[i].next){
            ll v=a[i].v,w=a[i].w;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
}

int main(){
    io; cin>>n>>m;
    ll u,v,w;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    for(int i=1;i<=n;i++) add(0,i,0);
    spfa();
    for(int i=1;i<=m;i++){
        u=a[i].u,v=a[i].v,w=a[i].w;
        printf("%lld %lld %lld\n",u,v,d[u]-d[v]+w);
    }
    return 0;
}