数据很恶心。。

负权环不一定和S相连。

编译通过...

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

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

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

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

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

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

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

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

Unaccepted 有效得分：85 有效耗时：0ms 什么病？

编译通过...

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

├ 测试数据 02：运行超时...

├ 测试数据 03：运行超时...

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

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

Unaccepted 有效得分：0 有效耗时：0ms

var

a:array[0..1000,0..1000] of longint;

d:array[0..1000] of longint;

n,m,s,t,i,j,k:longint;

x,y,z:longint;

change:boolean;

begin

readln(n,m,s);

for i:=0 to n do

for j:=0 to n do

if ij

then a:=maxint

else a:=0;

for i:=1 to m do

begin

readln(x,y,z);

a[x,y]:=z;

end;

for i:=1 to n do

d[i]:=a;

d:=0;

for k:=1 to n-1 do

for j:=0 to n do

for i:=0 to n do

if (amaxint)and(d[i]maxint)and(d[j]>d[i]+a) then

begin

d[j]:=d[i]+a;

end;

change:=true;

for i:=0 to n do

for j:=0 to n do

if d[j]>d[i]+a

then change:=false;

if change

then begin

for i:=1 to n do

begin

if d[i]=maxint

then writeln('NoPath')

else writeln(d[i]);

end;

end

else writeln(-1);

end.

请问各位高手

这是why！！！！！！！

SPFA判负环怎么做到0ms？？？

我交的快崩溃了！

编译通过...

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

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

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

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

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

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

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

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

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

SPFA

编译通过...

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

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

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

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

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

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

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

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

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

七七四十九，不吉利啊

45次的提交给后人提醒，最后1个点有正环，所以DFS的时候一定要判断dist是否小于0

超弱智的bellman-ford，为啥通过率贼低呢？

本人真粗心，交了快30次了，终于ac，0ms！

编译通过...

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

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

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

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

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

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

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

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

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

一次AC！

虽然代码很长，但是只要细心地去做，一样很容易AC！

话说dfs找负权回路咋弄。。我最后随机化5次spfa找的 - -！！

顶点不连通的图中有环..好可恶。。WA了N次。。

编译通过...

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

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

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

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

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

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

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

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

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

哎。没秒杀

太...艰难了

SPFA要加一个小小的优化

数组推荐把点当做2000来开

判断环，如果一个点入队次数>=n，则直接输出-1

循环变量全部Longint 其他全部Int64

注意：

1.有可能两点之间有多边，取最短的

2.S点不一定就在负圈上

注意有点到自己的负权边.饿新四卧乐.

竟然没发现这是有向图！我晕！

一道极其WS阴险的题目,经过长时间的努力,终于AC了。

bellmanford也可以零MS。

怎么用SPFA直接判断有无负权环？不是某节点入队的次数>=n么?

编译通过...

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

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

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

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

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

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

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

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

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

注意有重编，判断用DFS，最短路径用SPFA，秒杀掉！

交了好几次，数据有点苛刻！

判断负环要大于N

第345个过...

一定要用SPFA,挺快的,0ms

交了十几遍，终于AC了......

做法是在读入的时候把每个节点的边都记录下来，判断负权环的时候用

然后DFS找是否有负权环，有的话输出-1就HALT

没有的话就SPFA

总之，太艰难了.....