此题真恶心，为什么可以删边？难道不能走重复路吗？如果存在最短路，怎么可能不存在第二最短路？唯一的解释是.....标程出错，数据出错！我和楼下的大牛和楼下的楼下的神牛弄了一个下午

├ 测试数据 02：答案错误...

├ 标准行输出 1081...

　├ 错误行输出 659....

├ 测试数据 03：答案错误...

├ 标准行输出 641....

　├ 错误行输出 595....

├ 测试数据 05：答案错误...　

├ 标准行输出 263.5...

　├ 错误行输出 202.9...

明明是我们更优嘛

这是什么数据?

我在PKU上的有向有环有重边的, 可以s = e, 可以走重复路的图的第K短路的A*都AC了。

这里竟然70.

火嗤嗤得冒起来!

针对无向图，那个利用反边的次短路算法好难用。怎么也过不了。。我弱。。实力有限 还是乖乖删边把。。。

LX的牛错的三个点和我SPFA错的三个点一样。。。荣幸。。

记录最短路径，然后删去其中的某一些边。

但是这个方法明显有漏洞，在一个点可以走多次的时候...

当然，这里可以

floyd 枚举边总不对.................

第一次做删边dijkstra...

floyd求k短路+无敌常数优化=AC

注：此题严重卡floyd！！！！！！

晕。dj变量打错，WA了3次。

这个题目的数据的确小，用dj加删边就可以过。

否则要用传说中的k短路算法。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

简简单单。

就我会超时的……

From zhm_0525

集合位置 野猫江米 系列

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

AC得不明不白,谁发个程序

普通的删边就可以了

floyed做的，用到了序列归并

我用extended全错,real全对,晕!!

删边..

交了N次:枚举的时候忘了把删了的边还原了...

无限WA后顿悟..

AC~~100~~纪念一下啦~~

之前一直对一半是因为漏下无向图了~~

方法就是dj啦~~

谁告诉我floyd为什么错....过7个.....

用DJ和SPFA的我懂..

但为什么我用floyd算就不行呢..- -

难道某菜的算法错误..有没人能讲下用floyd算法来求K短路..

理论上K短路的求法：

因为最短路问题具有最优子结构，所以SPFA的时候保存每个状态的K优解，然后求解即可。

dijkstra,记录路径然后枚举删边，再做dijkstra