算法
(Dijkstra) $O(N(N + M\log M))$
显然从一点出发走回到自身的前提是该点在某个环内
由于数据规模不大,所以我们可以跑 $N$ 遍 Dijkstra
不懂为啥有人写spfa(虽然也能跑过)
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::greater;
using std::priority_queue;
using P = std::pair<int, int>;
struct E {
int to, co;
E(int to = 0, int co = 0): to(to), co(co) {}
};
int main() {
int n, m;
cin >> n >> m;
vector<vector<E>> g(n);
rep(i, m) {
int a, b, c;
cin >> a >> b >> c;
--a; --b;
g[a].emplace_back(b, c);
}
const int INF = 1001001001;
rep(sv, n) {
vector<int> dist(n, INF);
priority_queue<P, vector<P>, greater<P>> q;
auto push = [&](int v, int d) {
if (dist[v] <= d) return;
dist[v] = d;
q.emplace(d, v);
};
for (auto&& e : g[sv]) push(e.to, e.co);
while (q.size()) {
auto [d, v] = q.top(); q.pop();
if (dist[v] != d) continue;
for (auto&& e : g[v]) {
push(e.to, d + e.co);
}
}
int ans = dist[sv];
if (ans == INF) ans = -1;
cout << ans << '\n';
}
return 0;
}