求助：我的第2个点错了。。

测试数据 02：答案错误...程序输出比正确答案长

请大牛指教。。。。。。

我的做法：先dfs求出每个连通分支，然后spfa。。。

我来说一个简单的做法。

先把所有dis清0，把所有点加入队列，然后做SPFA，如果有点入队次数超过n次就算有负环，原理和bellmanford差不多。

没有负环就做一次正统SPFA求解便可。

注意：dis数组要用int64!!!!我为了这个WA了n次！！！

多谢前辈们的悉心教导……

本人终于AC了，耶！！

好多陷阱……好诡异的题目……

最诡异的是，第一个点我WA了，可评测机给我的却是Accepted！

Bellman-ford...

负权用搜的，后继用数组存储...

迭代的时候注意优化...

├ 测试数据 05：答案正确... 25ms

├ 测试数据 06：答案正确... 25ms

├ 测试数据 07：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：75ms

艰难啊...

鏖战到深夜0：45，最后终于AC了

我的第三百题，纪念下

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案错误...程序输出比正确答案长

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

---|---|---|---|---|---|---|---|-

郁闷

用C++的oier，不要用cin读数据啊，这里会超时啊，要用scanf

还有这道题要注意负圈可以不再源点的那个连通图中，而是在其他的连通图中

没用int64……

抓破头皮

AC了……用的前面的大牛们的方法……不过发现好像判断负环的方法有问题（虽然我这么AC了……仔细想想还是不太对）

如果只是用dist2 2->3 3->4 4->2 边权都是-1

反正我的程序就死循环了……

貌似有向图只能用判断N+1次入队那个方法（无向图没想到反例）

不知道有没有大牛解释下……

Accepted 有效得分：100 有效耗时：119ms 我变成救火的了……

此题做法很简单，就是SPFA(Bellman_Ford我没试)，但是一次做对难度太大了

好多陷阱.......

1,只要有负环就输出-1

2,第7个点错是因为每两个点之间不止一条边......

我的做法是这样的:

1.用dfs判断是否有负权环(此方法可以判断所有的负权环);

2.使用SPFA求最短路;(此时无需在SPFA里判断环了);

3.注意细节.

本人也因为一些细节问题,用马甲WA了N次,不过最后终于搞定了!

解法一：

朴素Bellman-Ford不影响出解，只要加一个数组记录dist[i]所标识的最短路的长度

还有个数组初值全为0.

★记录最短路径和判断负环不能兼容。

在Dolphin下貌似要超时。

解法二：

SPFA

当dist

输入时需做处理,保留两点之间最短的那条路径 而不是后来输入的覆盖先输入的

对于图可以按连通性分成多个图做负权回环的检查

对每个连通的图做SPFA,有负权回环的特征即dist

SPFA+SPFA

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：运行时错误...|错误号: -1073741819

├ 测试数据 05：运行时错误...|错误号: -1073741819

├ 测试数据 06：运行时错误...|错误号: -1073741819

├ 测试数据 07：运行时错误...|错误号: -1073741819

搞什么飞机

哪位大牛救救我的spfa

终于AC了。

SPFA求最短路径，并判断回路。

当dist

*判断非负权环

...

while xnil do

begin

v:=x^.p;

if t+x^.w

乱写的bellmanford

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案错误...程序输出比正确答案长

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 509ms

├ 测试数据 07：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：509ms

• -弱弱的SPFA
  

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案错误...程序输出比正确答案长

├ 测试数据 04：答案正确... 369ms

├ 测试数据 05：答案正确... 56ms

├ 测试数据 06：答案正确... 994ms

├ 测试数据 07：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：85 有效耗时：1419ms

吐血。。

谢谢前面的大牛，dfs都是0m过啊