注意 h 大得离谱的范围,刚好卡着 long long 的上界,所以最好的处理方式,其一就是全程 unsigned long long 或者 __int128_t,还有一种方法就是设 −1 为 ∞,但我尝试了没成功(实现太丑陋),还有一个更巧妙的就是根据同余最短路的本质将 h 自减 1 后把 inf 设为 263−1,也就是 long long 的上界。
至于数据过水,指的是我把
if(!Vis[v]) Q.push(v),Vis[v]=1;
写成
if(!Vis[v]) Q.push(v),Vis[u]=1;
有 80pts。
写成
if(!Vis[v]) Q.push(v),Q.push(v);
有 50pts。
而题解区中大多数人直接 std::memset(f,0x3f,sizeof(f)) 应该都是过不了的,可能现在还没 hack(?