虽然我过了这题（900+ms）。但是我的 DIJ 算法在其他地方被卡了。

如果你的 dij 是这么写的：

while(){
 vis[x] = 1;
 ...
 if(!vis[y]) q.push(y);
}

可能你的队列是这样的

$\dots x,y,z,x,y,z,x,y,z\dots$。

每个 $x,y,z$ 都会被执行一遍，然后套娃。

这样复杂度可能退化成 $\mathcal O(n^2\log n)$ 的。