1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <bits/stdc++.h>
using dist_t = int;
struct Edge {
int v;
dist_t w;
};
using AdjList = std::vector<std::vector<Edge>>;
using AdjMatrix = std::vector<std::vector<dist_t>>;
std::optional<std::vector<dist_t>> bellmanford(const AdjList& G, int s) {
constexpr dist_t inf = std::numeric_limits<dist_t>::max() / 2;
std::vector<dist_t> dist(G.size(), inf);
std::vector<int> cnt(G.size());
std::vector<bool> vi(G.size());
dist[s] = 0, vi[s] = true;
std::queue<int> q({s});
while (!q.empty()) {
int u = q.front();
q.pop();
vi[u] = false;
for (auto&& [v, w] : G[u])
if (dist_t dv = dist[u] + w; dv < dist[v]) {
dist[v] = dv;
if ((cnt[v] = cnt[u] + 1) >= G.size()) return std::nullopt;
if (!vi[v]) q.emplace(v), vi[v] = true;
}
}
return dist;
}
std::vector<dist_t> dijkstra(const AdjList& G, int s) {
std::vector<dist_t> dist(G.size(), std::numeric_limits<dist_t>::max() / 2);
dist[s] = 0;
using item = std::pair<dist_t, int>;
std::priority_queue<item, std::vector<item>, std::greater<item>> pq;
pq.emplace(0, s);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto&& [v, w] : G[u])
if (dist_t dv = dist[u] + w; dv < dist[v]) pq.emplace(dist[v] = dv, v);
}
return dist;
}
std::optional<AdjMatrix> johnson(AdjList&& G) {
const int N = G.size();
auto& new_node = G.emplace_back();
new_node.reserve(N);
for (int i = 0; i < N; ++i) new_node.emplace_back(Edge{i, 0});
auto h_ = bellmanford(G, N);
if (!h_.has_value()) return std::nullopt;
auto& h = *h_;
for (int u = 0; u <= N; ++u)
for (auto& [v, w] : G[u]) w += h[u] - h[v];
AdjMatrix dist;
dist.reserve(N);
for (int u = 0; u < N; ++u) {
auto& row = dist.emplace_back(dijkstra(G, u));
row.pop_back();
for (int v = 0; v < N; ++v) row[v] += h[v] - h[u];
}
return dist;
}
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int N, M;
cin >> N >> M;
AdjList G(N);
for (int i = 0; i < M; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
G[u].emplace_back(Edge{v, w});
}
auto adj = johnson(std::move(G));
if (!adj.has_value()) {
cout << "-1";
return 0;
}
for (auto&& row : *adj) {
ll res = 0;
for (int v = 0; v < N; ++v) res += ll(v + 1) * min(row[v], dist_t(1e9));
cout << res << '\n';
}
}
|