P5905 【模板】全源最短路（Johnson）

//负权多源最短路 约翰逊算法 (nmlogn)
#include<bits/stdc++.h>
#define INF 1000000000
#define LL long long
using namespace std;
const int N=30005;
int n, m;
struct edge{ int v, w; };
vector<edge> e[N];
int vis[N], cnt[N];
LL h[N], d[N];void spfa() {queue<int> q;memset(h, 0X3F, sizeof h);memset(vis, false, sizeof vis);h[0]=0, vis[0]=1; q.push(0);while(!q.empty()) {int u=q.front(); q.pop(); vis[u]=0;for(auto ed : e[u]) {int v=ed.v, w=ed.w;if(h[v] > h[u]+w) {h[v]=h[u]+w;cnt[v]=cnt[u]+1;if(cnt[v] > n) {printf("-1\n"); exit(0);}if(!vis[v]) q.push(v), vis[v]=1;}}}
}void dijkstra(int s) {priority_queue<pair<LL, int>> q;for(int i=1; i <= n; i++) d[i]=INF;memset(vis, false, sizeof vis);d[s]=0; q.push({0, s});while(!q.empty()) {int u=q.top().second; q.pop();if(vis[u]) continue;vis[u]=1;for(auto ed : e[u]) {int v=ed.v, w=ed.w;if(d[v] > d[u]+w) {d[v]=d[u]+w;if(!vis[v]) q.push({-d[v], v});}}}
}int main() {cin >> n >> m;for(int i=1, u, v, w; i <= m; i++)cin >> u >> v >> w, e[u].push_back({v, w});for(int i=1; i <= n; i++)e[0].push_back({i, 0}); //加虚拟边spfa();for(int u=1; u <= n; u++)for(auto &ed : e[u])ed.w+=h[u]-h[ed.v];//构造新边for(int i=1; i <= n; i++) {dijkstra(i);LL ans=0;for(int j=1; j <= n; j++) {if(d[j] == INF) ans+=(LL)j*INF;else ans+=(LL)j*(d[j]+h[j]-h[i]);}printf("%lld\n", ans);}return 0;
}