#2392. Johnson 全源最短路

题目描述
给定一个包含 n 个结点和 m 条带权边的有向图，求所有点对间的最短路径长度，一条路径的长度定义为这条路径上所有边的权值和。

注意：

边权可能为负，且图中可能存在重边和自环；
部分数据卡 n 轮 SPFA 算法。
输入格式
第 1 行：2 个整数 n,m，表示给定有向图的结点数量和有向边数量。

接下来 m 行：每行 3 个整数 u,v,w表示有一条权值为 w 的有向边从编号为 u 的结点连向编号为 v 的结点。

输出格式
若图中存在负环，输出仅一行 ?1。

若图中不存在负环：

输出 n 行：令 dis{i,j}
i,j
?
为从 i 到 j 的最短路，在第 i 行输出 \sum\limits_{j=1}^n j\times dis_{i,j}
j=1
∑
n
?
j×dis
i,j
?
，注意这个结果可能超过 int 存储范围。

如果不存在从 i 到 j 的路径，则 dis_{i,j}=10^9dis
i,j
?
=10
9
；如果 i=j则 dis{i,j}
?
=0。

样例 #1
样例输入 #1
5 7
1 2 4
1 4 10
2 3 7
4 5 3
4 2 -2
3 4 -3
5 3 4
样例输出 #1
128
1000000072
999999978
1000000026
1000000014
样例 #2
样例输入 #2
5 5
1 2 4
3 4 9
3 4 -3
4 5 3
5 3 -2
样例输出 #2
-1

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define int ll 

const int N = 16666;
const int inf = 1e9;

struct Edge {
	int nxt;
	int to;
	int w;
}e[N];

int head[N], edge_num = 0;

inline void add_edge (int x, int y, int z) {
	e[++ edge_num].to = y;
	e[edge_num].nxt = head[x];
	e[edge_num].w = z;
	head[x] = edge_num;
} 

int n, m, indeg[N], inque[N];

int d[N];

inline bool SPFA (int s) {//SPFA判断负环。 
	for (int i = 1; i <= n; i ++) {
		d[i] = inf;
	}
	memset (inque, false, sizeof (inque));
	
	queue<int> qwq;
	
	qwq.push(s);
	
	d[s] = 0, inque[s] = true;
	
	indeg[s] ++;
	
	while (!qwq.empty()) {
		int u = qwq.front();
		
		qwq.pop();
		
		inque[u] = false;
		
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			
			if (d[v] > d[u] + e[i].w) {
				d[v] = d[u] + e[i].w;
				
				if (inque[v] == false) {
					qwq.push (v);
					
					inque[v] = true;
					
					indeg[v] ++;
						
					if (indeg[v] >= n + 1) {
						return true;
					}
				}
			}
		}
	}
	
	return false;
}

int dis[N];

bool vis[N];

inline void Dij (int s) {//求单源最短路径。 
	for (int i = 1; i <= n; i ++) {
		dis[i] = inf;
	}
	
	memset (vis, false, sizeof (vis));
	
	priority_queue<pii, vector<pii>, greater<pii> > q; 
	
	dis[s] = 0;
	
	q.push (make_pair(0, s));
	
	while (!q.empty()) {
		int u = q.top().second;
		
		q.pop();
		
		if (vis[u]) {
			continue;
		}
		
		vis[u] = true;
		
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			
			if (dis[v] > dis[u] + e[i].w) {
				dis[v] = dis[u] + e[i].w;
				
				if (vis[v] == false) {
					q.push (make_pair(dis[v], v));
				}
			}
		}
	}
}

signed main() {
	scanf ("%lld%lld", &n, &m);
	for (int i = 1, x, y, z; i <= m; i ++) {
		scanf ("%lld%lld%lld", &x, &y, &z);
		
		add_edge (x, y, z);
	}
	
	for (int i = 1; i <= n; i ++) {
		add_edge (0, i, 0);
	}
	
	if (SPFA (0) == true) {
		//出现负环无解。 
		printf ("-1");
		
		return 0;
	}
	
	for (int i = 1; i <= n; i ++) {
		for (int j = head[i]; j; j = e[j].nxt) {
			int v = e[j].to;
			
			e[j].w += d[i] - d[v]; //使边权满足非负性。 
		}
	}
	
	for (int i = 1; i <= n; i ++) {
		Dij (i);
		
		ll ans = 0;
		
		for (int j = 1; j <= n; j ++) {
			if (dis[j] == inf) {
				ans += 1ll * inf * j;
			}
			
			else {
				ans += 1ll * j * (dis[j] - d[i] + d[j]);//要将其减去。 
			}
		}
		
		printf ("%lld\n", ans);
	} 
	
	return 0;
}