囧编译通过... ├ 测试数据 01：答案正确... 0ms ├ 测试数据 02：答案正确... 0ms ├ 测试数据 03：答案错误...程序输出比正确答案长 ├ 测试数据 04：答案正确... 0ms ├ 测试数据 05：答案正确... 0ms ├ 测试数据 06：答案错误...程序输出比正确答案长 ├ 测试数据 07：答案错误...　├ 标准行输出 　├ 错误行输出 ------------------------- Unaccepted 有效得分：45 有效耗时：0ms 

提交了26遍

甚至照标程改了n遍

但始终没A

最后的教训是

c++一定要用scanf和printf

不能用cin和cout！！！

郁闷啊。。。第七个数据怎么回事会比正解小...我连两点多路都处理了啊。。。

编译通过...

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

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

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

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

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

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

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

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

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

A了！虽然不是巨快如闪电

就是先对s用spfa，如果没有出现负权环就对与s不连通的点spfa

纠结啊，还是过了。。

感觉dfs n*n 不能判断负环啊。

应该是cheat吧。

对每个连同块。spfa才是王道

编译通过...

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

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

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

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

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

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

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

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

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

判断环有个很好的优化

while(op < cl)

{

k = q[op];

v[k] = true;

for(j = e[k] ; j != -1 ; j = edge[j].next)

{

i = edge[j].t;

if(d[k] + edge[j].v < d[i])

{

d[i] = d[k] + edge[j].v;

if(!inq[i])

{

inq[i] = true;

q[cl] = i;

cl++;

co[i]++;

if(co[i] >= n - 1)return -1;

}

}

}

inq[k] = false;

op++;

if(d < 0) //在这里是一个环的优化

{

return -1;

}

}

经过无数次提交wa的惨痛教训，第2组显示标准输出比选手输出长的同学注意判断负环的时候要写>n 不能写 >=n 啊！！！

lx正解，，此题最ws的地方就是和s不连的负环。。哎，，阴险啊。。是说这通过率....

编译通过...

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

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

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

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

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

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

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

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

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

数据弱，每个联通块只要SPFA一下找负权环就行了。没出那种用每个联通块的第一个点做SPFA会出错的数据。比如

4 4 1

1 2 5

2 3 -1

3 4 -1

4 2 -1

我们用1做SPFA，显然没办法找到负权环2 3 4。

所以深搜找负权环比较好。但是我太菜了，以至于老超时，于是用上述方法cheat了。实在囧啊！

35次提交后得到的教训。。。要用int64，初值要大一些

为啥你们能秒杀。。

1.居然有不和S在一个连通块里面的负环。。。。。

2.不看题解不知道。。。读进来的可能有重边。。要取最小的那个。。orz

后来者注意。。

这个题好猥琐~~~

编译通过...

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

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

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

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

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

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

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

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

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

哪位大哥请写出题其解！

自己到自己的负边。。。。。。

还可以再WS点

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

建议楼下的别用int64，我就是这样挂的.......

听题解用了int64=90分，用longint=100分，这到底是为什么啊.....

编译通过...

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

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

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

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

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

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

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

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

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

90分？

编译通过...

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

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

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

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

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

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

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

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

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

经过13次提交 我终于AC了........

深搜判无解 每次都找负权边 注意可能有重边

选值最小的那个记录 用a记录即可

搜过的点在同一次搜索中再出现就是无解

近似O(N^2)DFS+O(2E)SPFA=秒杀

编译通过...

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

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

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

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

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

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

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

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

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

我看见了这个...