本题主流有三种解法：Floyd，n轮Dijestra和n轮SPFA。Floyd用的最多，但却是最慢的(n^3)，根据P<=500可得循环次数直逼1E8，完全可能被卡掉，但我的Floyd写出来后最慢的点才90多ms，可见数据不强。

相比之下，n轮Dijestra(nmlogn)明显更快，SPFA(nklogn)虽然死了，若退化至(n^2m)循环次数可达2E8，不过本题图也并不算稠密。总的来讲，如果本题通过构造卡掉Floyd，保留D和S的做法，会成为更好的一道题