单源最短路
spfa
int dis[N],vis[N],cnt[N],nw;
struct edge{int v,w;};
vector<edge> e[N];
queue<int> sp;
il bool spfa(int st,int n){
for(ri int i=1;i<=n;++i) dis[i]=inf;
dis[st]=0,sp.push(st),vis[st]=1;
while(!sp.empty()){
nw=sp.front(),sp.pop(),vis[nw]=0;
for(ri unsigned int i=0;i<e[nw].size();++i){
if(dis[nw]+e[nw][i].w<dis[e[nw][i].v]){
dis[e[nw][i].v]=dis[nw]+e[nw][i].w;
cnt[e[nw][i].v]=cnt[nw]+1;
if(cnt[e[nw][i].v]>=n) return 0;
if(!vis[e[nw][i].v]){
vis[e[nw][i].v]=1;
sp.push(e[nw][i].v);
}
}
}
}
return 1;
}
dijkstra
int dis[N],vis[N];
struct edge{int v,w;};
vector<edge> e[N];
struct qwq{
int u,we;
bool operator < (const qwq &o) const{
return we>o.we;
}
}ow,oo;
priority_queue<qwq> dij;
il void dijkstra(int st,int n){
for(ri int i=1;i<=n;i++) dis[i]=inf;
dis[st]=0;
ow=(qwq){st,dis[st]};
dij.push(ow);
while(!dij.empty()){
ow=dij.top();
dij.pop();
if(vis[ow.u]) continue;
vis[ow.u]=1;
for(ri unsigned int i=0;i<e[ow.u].size();++i){
if(dis[e[ow.u][i].v]>dis[ow.u]+e[ow.u][i].w){
dis[e[ow.u][i].v]=dis[ow.u]+e[ow.u][i].w;
oo=(qwq){e[ow.u][i].v,dis[e[ow.u][i].v]};
dij.push(oo);
}
}
}
return;
}
全源最短路
Johnson
边权可能为负，且图中可能存在重边和自环
namespace edge{
struct ovo{int v,w;};
vector<ovo> e[N];
}
namespace Spfa{
using namespace edge;
queue<int> s;
int dis[N],cnt[N];
bool vs[N];
il bool spfa(int st,int n){
for(ri int i=1;i<=n;++i) dis[i]=inf;
ri int u;s.push(st),dis[st]=0,vs[st]=1;
while(!s.empty()){
u=s.front(),s.pop(),vs[u]=0;
for(ovo o:e[u]){
if(dis[u]+o.w<dis[o.v]){
dis[o.v]=dis[u]+o.w;
cnt[o.v]=cnt[u]+1;
if(cnt[o.v]>n) return 1;
if(!vs[o.v]){
s.push(o.v),vs[o.v]=1;
}
}
}
}
return 0;
}
}
namespace dijkstra{
using namespace edge;
int dis[N]; bool vs[N];
struct qwq{
int u,dis;
bool operator<(cs qwq o)cs{
return dis>o.dis;
}
};
priority_queue<qwq> d;
il void dij(int st,int n){
for(ri int i=1;i<=n;++i) dis[i]=inf,vs[i]=0;
dis[st]=0;ri int u;
d.push({st,dis[st]});
while(!d.empty()){
u=d.top().u,d.pop();
if(vs[u]) continue;
vs[u]=1;
for(ovo o:e[u]){
int w=o.w+Spfa::dis[u]-Spfa::dis[o.v]; // 重新设置边权
if(w+dis[u]<dis[o.v]){
dis[o.v]=w+dis[u];
d.push({o.v,dis[o.v]});
}
}
}
return;
}
}
il void Johnson(int n){
for(ri int i=1;i<=n;++i){
edge::e[0].push_back({i,0});
} // 新建一个虚拟节点，从这个点向其他所有点连一条边权为 0 的边。
if(Spfa::spfa(0,n)) return puts("-1"),0;
//预处理跑一遍 Bellman-Ford ( spfa 是 Bellman-Ford 的一种优化 )
for(ri int i=1,as;i<=n;++i){
dijkstra::dij(i,n),as=0;
for(ri int j=1;j<=n;++j){
if(dijkstra::dis[j]==inf) as+=j*(1e9);
else as+=j*(dijkstra::dis[j]+Spfa::dis[j]-Spfa::dis[i]);
}
wt(as),putchar('\n');
}
}