U645546 【模板】单源最短路经

# 本题很卡SPFA [【模板】单源最短路径（标准版）](https://www.luogu.com.cn/problem/P4779) 你需要设计一个spfa __优化__ 版本，使其可以通过此题 本题难度不作参考

给定一个 $n$ 个点，$m$ 条有向边的图（不保证无负权边），请你计算从 $s$ 出发，到每个点的距离。 数据不保证你能从 $s$ 出发到任意点，如不能到达，输出 $4557430888798830399$ (0x3f3f3f3f3f3f3f3f)。

第一行为三个正整数 $n,m,s$ 。 第二行起 $m$ 行，每行三个整数 $u , v , w $ ，表示从 $u$ 到 $v$ 有一条权值为 $w$ 的有向边。

如果有负环，输出`No answer.` 否则输出，一行 n 个空格分隔的整数，表示 s 到每个点的距离。

$1≤n≤8 \times 10^5 ；$ $1≤m≤2 \times 10^6 ；$ $1≤u,v≤n；$ $w\in[-10^{9},10^{9}]。$ 更强数据见[【模板】单源最短路经 2](https://www.luogu.com.cn/problem/U645547) ### 为了防止有人说这题是错题，善良的出题人@[pengyulun](/user/1545565) 将 TA 的其中一个数据点标程公开： ```cpp #include using namespace std; #define int long long int n=8e5,m=2e6,mod=1e9,s[800005]; inline int rad(){ queue q; return q.front(); } struct node{int x,y,z;}; vector a; inline int rd(int l,int r){ int w; while (!(0