Johnson 全源最短路学习笔记
模板传送门
考虑\(n\)次用优先队列优化的\(dijkstra\)，时间复杂度\(O(nm \log m)\)。
但是因为\(dijkstra\)是能求边权为正的图
考虑将所有边权转化为正，构造虚拟节点\(0\)，向所有点连接一条边权为\(0\)的边，以\(0\)为开始跑一次\(spfa\)，若有负环则输出\(-1\)，否则将\(0->en\)的最短路记录到\(h_{en}\)中，然后将每条边\(u->v\)加上边权\(h_u-h_v\)
\(1\)、这样的边权必然非负，若我们如此操作，\(h_u-h_v\)为\(0->v\)的最短路比\(0->u\)的最短路短多少，若最短路为\(0->u->v\)，则边权\(e_{u->v}\)加上\(h_u-h_v\)为0，若最短路为其他，则该差值一定比\(e_{u->v}\)小（不然的话会走\(u->v\)），\(e_{u->v}\)加上\(h_u-h_v\)大于\(0\)
\(2\)、这样做不会对结果的正确性产生影响，若我们如此操作，所有\(u->v\)路径权值和为
\[e_{u->a_1}+h_u-h_{a_1}+e_{a_1->a_2}+h_{a_1}-h_{a_2}+...+e_{h_x->a_v}+h_x-h_v=e_{u->a_1}+e_{a_1->a_2}+...+e_{h_x->a_v}+h_u-h_v
\]
容易发现，无论走那条路，\(u->v\)的总边权都加上了\(h_u-h_v\)，我们只要用\(dijkstra\)求出\(u->v\)的最短路减去\(h_u-h_v\)即可
上代码：
#include<bits/stdc++.h>
#define ll long long
#define PLL pair<ll,ll>
using namespace std;
const ll N=3e3+50,M=6e3+50,INF=1e9;
ll n,m;
ll head[N+N],e[M+N],ne[M+N],w[M+N],idx;
void add(ll a,ll b,ll c)
{
e[idx]=b;
w[idx]=c;
ne[idx]=head[a];
head[a]=idx++;
}
ll h[N],t[N],dis[N];
bool vis[N];
bool spfa(ll st)
{
queue<int> q;
memset(h,0x3f3f3f3f3f3f,sizeof h);
h[st]=0;
vis[st]=true;
q.push(st);
while(!q.empty())
{
ll now=q.front();
q.pop();
vis[now]=false;
for(ll i=head[now];i!=-1;i=ne[i])
{
ll j=e[i];
if(h[j]>h[now]+w[i])
{
h[j]=h[now]+w[i];
if(!vis[j])
{
vis[j]=true;
q.push(j);
t[j]++;
if(t[j]==n+1) return false;
}
}
}
}
return true;
}
void dijkstra(ll st)
{
priority_queue<PLL,vector<PLL>,greater<PLL> > q;
for(ll i=1;i<=n;i++) dis[i]=INF;
memset(vis,false,sizeof vis);
dis[st]=0;
q.push({dis[st],st});
while(!q.empty())
{
ll now=q.top().second;
q.pop();
if(vis[now]) continue;
vis[now]=true;
for(ll i=head[now];i!=-1;i=ne[i])
{
ll j=e[i];
if(dis[j]>dis[now]+w[i])
{
dis[j]=dis[now]+w[i];
q.push({dis[j],j});
}
}
}
return ;
}
int main()
{
memset(head,-1,sizeof head);
scanf("%lld %lld",&n,&m);
for(ll i=1;i<=m;i++)
{
ll a,b,c;
scanf("%lld %lld %lld",&a,&b,&c);
add(a,b,c);
}
for(ll i=1;i<=n;i++)
add(0,i,0);
if(!spfa(0))
{
printf("-1\n");
return 0;
}
for(ll st=1;st<=n;st++)
for(ll i=head[st];i!=-1;i=ne[i])
w[i]=w[i]+h[st]-h[e[i]];
for(ll i=1;i<=n;i++)
{
dijkstra(i);
ll ans=0;
for(ll j=1;j<=n;j++)
if(dis[j]==INF)
ans=ans+j*INF;
else
ans=ans+j*(dis[j]+h[j]-h[i]);
printf("%lld\n",ans);
}
return 0;
}