primality

想把 spfa 换成 dij，用 Johnson 里面的技巧，给予每个点一个势能 \(h_u\)，边 \((u,v,w)\) 的新边权为 \(w+h_u-h_v\)，为了保证其 \(\geq 0\) 以源点为最短路跑最短路后赋值 \(h_u\gets d_u\) 即可。 增广之后会加入反向边，考虑怎 ......

# Johnson 全源最短路算法 Floyd 可以 $O(n^3)$ 处理全源最短路，Bellman-Ford 单源最短路的复杂度是 $O(nm)$ 的，Dijkstra 可以做到 $O(m\log m)$ 但不能处理负边权，所以 Johnson 全源最短路算法通过处理使得可以用 $n$ 次 Di ......

# 题目地址 https://ac.nowcoder.com/acm/contest/57677/A # 代码 ``` use std::io::{self, BufRead, Write}; fn is_prime_triival(n: i128) -> bool { if n i128 { le ......