思路分析
1. 判断负环
这个部分相对来说比较简单，可以用经典的 SPFA 算法判断负环，时间复杂度 \(O(nm)\)。这里给出一种效率更高的负环判断方法，使用 DFS 判断负环。遍历这个图，进行松弛技术，如果一个节点被访问第二次，那么就说明存在负环，直接退出。时间复杂度 \(O(n)\)。
void fuhuan(int s){vis[s]=1;for(int i=h[s];i!=-1;i=e[i].nxt){if(d[e[i].to]>d[s]+e[i].w){if(vis[e[i].to]||flag){flag=1;break;}d[e[i].to]=d[s]+e[i].w;fuhuan(e[i].to);}}vis[s]=0;
}
如果找到了负环直接输出 \(-1\)，跳出。
2. 新建节点，找最短路
这一部分是在为后面的算法核心做预处理。新建一个 \(0\) 节点连到所有节点上，然后从 \(0\) 节点跑一遍 SPFA 找到 \(0\) 距离所有节点的最短路。时间复杂度 \(O(nm)\)。
void SPFA(int s){memset(d,0x3f,sizeof(d));memset(vis,0,sizeof(vis));d[s]=0;q.push(s);vis[s]=1;while(!q.empty()){int t=q.front();q.pop();vis[t]=0;for(int i=h[t];i!=-1;i=e[i].nxt){int v=e[i].to;if(d[v]>d[t]+e[i].w){d[v]=d[t]+e[i].w;if(vis[v]==0){q.push(v);vis[v]=1;}}}}
}
for(int i=1;i<=n;i++){Add(0,i,0);
}
SPFA(0);
3. 重置边权
这一部分是 Johnson 算法的核心，目的是使用更高效的 Dijkstra 算法求带有负边权的最短路。怎么实现呢？我们从 \(0\) 节点跑过一次最短路。设 \(u\) 节点到 \(0\) 节点的最短路是 \(h_u\)，与 \(u\) 相连的节点是 \(v\)。因为 \(h_u\) 和 \(h_v\) 都是松弛技术得来的最短路，那么对于原图中的边权 \(w(u,v)\)，则有 \(h_u+w(u,v) \ge h_v\)。那么 \(h_u - h_v\) 就大于等于 \(-w(u,v)\)，也就是原边权的相反数。于是把每条边的边权全部加上 \(h_u-h_v\)，就可以保证边权全部非负，可以使用 Dijkstra 算法求解最短路。
为什么这么处理是正确的呢？我们不妨把这样求解的一条最短路展开，其中 \(s\) 为起点，\(e\) 为终点，\(p_i\) 是中间经过的点，共经过了 \(k\) 个点，可得：
化简整理，得：
可以发现，所有中间的值都约掉了，只剩下 \(h_s-h_e\) 这一个值。那么它就相当于一个偏移量，不影响最短路求解。
此部分时间复杂度为 \(O(m)\)。
for(int i=1;i<=m;i++){e[i].w=e[i].w+d[e[i].from]-d[e[i].to];
}
4. 求解最短路
使用 Dijkstra 的堆优化对每个节点分别求解单元最短路，套板子即可。时间复杂度 \(O(nm \log m)\)，优于 SPFA 的 \(O(n^2m)\)，而且 SPFA 经常会被卡退化成 Bellman-Ford，变成 \(O(n^3m)\)。
void dijkstra(int s){memset(vis,0,sizeof(vis));d2[s][s]=0;q2.push((Heapnode){0,s});while(!q2.empty()){Heapnode front=q2.top();q2.pop();int w=front.w,u=front.u;if(vis[u]) continue;vis[u]=1;for(int i=h[u];i!=-1;i=e[i].nxt){int v=e[i].to;if(d2[s][v]>d2[s][u]+e[i].w){d2[s][v]=d2[s][u]+e[i].w;if(!vis[v]){q2.push((Heapnode){d2[s][v],v});}}}}
}
5. 统计答案，输出
按题意来即可。记得减去先前的偏移量。
for(int i=1;i<=n;i++){ans=0;for(int j=1;j<=n;j++){if(d2[i][j]==0x3f3f3f3f3f3f3f3f){ans+=1000000000*j;}else{ans+=(d2[i][j]-d[i]+d[j])*j;}}printf("%lld\n",ans);
}
完整代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define int long long
using namespace std;
const int maxn=3e3+10;
const int maxm=6e3+10;
struct Node{int from,to,nxt,w;
}e[maxm+maxn];
int n,m;
int h[maxn],tot,ans;
int d[maxn],d2[maxn][maxn],iqcnt[maxn];
bool vis[maxn],flag;
queue<int>q;
struct Heapnode{int w,u;bool operator <(const Heapnode &x) const{return w>x.w;}
};
priority_queue<Heapnode>q2;
void Add(int u,int v,int w){tot++;e[tot].from=u;e[tot].to=v;e[tot].nxt=h[u];e[tot].w=w;h[u]=tot;
}
void fuhuan(int s){vis[s]=1;for(int i=h[s];i!=-1;i=e[i].nxt){if(d[e[i].to]>d[s]+e[i].w){if(vis[e[i].to]||flag){flag=1;break;}d[e[i].to]=d[s]+e[i].w;fuhuan(e[i].to);}}vis[s]=0;
}
void SPFA(int s){memset(d,0x3f,sizeof(d));memset(vis,0,sizeof(vis));d[s]=0;q.push(s);vis[s]=1;while(!q.empty()){int t=q.front();q.pop();vis[t]=0;for(int i=h[t];i!=-1;i=e[i].nxt){int v=e[i].to;if(d[v]>d[t]+e[i].w){d[v]=d[t]+e[i].w;if(vis[v]==0){q.push(v);vis[v]=1;}}}}
}
void dijkstra(int s){memset(vis,0,sizeof(vis));d2[s][s]=0;q2.push((Heapnode){0,s});while(!q2.empty()){Heapnode front=q2.top();q2.pop();int w=front.w,u=front.u;if(vis[u]) continue;vis[u]=1;for(int i=h[u];i!=-1;i=e[i].nxt){int v=e[i].to;if(d2[s][v]>d2[s][u]+e[i].w){d2[s][v]=d2[s][u]+e[i].w;if(!vis[v]){q2.push((Heapnode){d2[s][v],v});}}}}
}
signed main(){memset(h,-1,sizeof(h));memset(d,0x3f,sizeof(d));scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++){int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);Add(u,v,w);}for(int i=1;i<=n;i++){if(!vis[i]) fuhuan(i);}if(flag){printf("-1");return 0;} for(int i=1;i<=n;i++){Add(0,i,0);}SPFA(0);for(int i=1;i<=m;i++){e[i].w=e[i].w+d[e[i].from]-d[e[i].to]; }memset(d2,0x3f,sizeof(d2));for(int i=1;i<=n;i++){dijkstra(i);}for(int i=1;i<=n;i++){ans=0;for(int j=1;j<=n;j++){if(d2[i][j]==0x3f3f3f3f3f3f3f3f){ans+=1000000000*j;}else{ans+=(d2[i][j]-d[i]+d[j])*j;}}printf("%lld\n",ans);}return 0;
}
一些坑点
- 建完 \(0\) 点的所有边后边的总量是 \(n+m\) 条，空间别开小了（本人曾喜提 \(76\) pts RE）；
long long用memset初始化，最后判断的时候记得输对（比如0x3f就不是int类型的0x3f3f3f，而是0x3f3f3f3f3f3f3f3f）。
总结
这个题考察了几个求最短路的模板，以及修改负权的方法。虽然实际情况使用不多，但是仍然给我们提供了一条宝贵的思路。
总时间复杂度 \(O(nm \log m)\)。