英文说的是他的路径的长度是 $\leq 1000$ 的，并没有说他们两点之间的的最短路是 $\leq 1000$，因为 $1000 \times 300 \times 300$ 是不会爆 int 的，但却 WA on test 38。去codeforces上看了眼数据，发现 $d_{i,j}$ 并不是 $\leq 1000$ 的，好像是 0 1000 2000 3000.....。

所以要开 long long。