DFS 也可以.

推荐SPFA 练练手.

第八组数据有错?

用DFS!!!很简单 也不长

囧~

1和5 WA了~

总长度一样的，只是和答案输出的路不同~

无语第8组数据，竟然存在环。

无奈的CHEAT之...

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

Then...

编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms-------------------------Accepted 有效得分：100 有效耗时：0ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我用的spfa,修改了一下，求最长路径。显然不像楼下的说的那样需要两次spfa，我只用了1次，然后dfs找路径。写了近80行。

ms这题用关键路径更好写，需要学习一下了.^_^

为什么总是不能ac

用搜索的办法，

吧 谁能告诉我

终于明白了，

第二问求的不是一条关键路径上的点，

是所有最长路径上的点……

搜一下就可以了

我不知是我理解有误还是如何。

确实要像楼下下下……的同学那样SPFA(BellmanFord)两次才行。

否则只能得到80分。

不过感觉这样仍旧不完备，甚至是个错的=_=bb...

例如：

4 6

1 2 1

2 5 1

1 3 1

3 5 1

1 4 1

4 5 1

应该是

2

1 2 3 4 5

如果spfa两次的话是

1 2 4 5.

所以本题不适合用spfa..=_=

无语，第8组就是过不了

坚持到现在不容易啊,好歹抢到了第一百个.

虽然本人向来不喜欢cheat..但是,为了上榜这个荣誉,霍出去了.

怪怪的这题目.算法实在应该没错什么啊.

VIJOS现在又故作高级,不让骗数据,还真不知道错在哪里.

就这样吧,坚持不下去了....

哎,花了我3个小时,结果写了个搜索过了...程序40来行也...

什么叫关键路径？

如果这题 起点为1---|-5 中间尽量多找点。。。。

意思就是找最大环， 如果有几个同样大的环，那么比较权值，是这样吗？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

拓扑排序+关键路径

CHEAT第8组数据 总觉得第8组数据有错。。。

有没有人可以解释一下样例？

图里面没有圈！我用深搜提交了一遍！

那就是纯粹的求关键路径了，那我怎么会WA第8点。。。。。太奇怪恶劣。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Bellman-Ford可以求负权最短路径,,同样方法也可以求正权最长路径,,但是最好求两次,,1次是如果找到1条路径长于当前以求路径的时候更改,,另1次是当如果找到1条路径不短于当前以求路径的时候更改,,把两次都经过的点存起来再排序输出(我是用f[1..101]:boolean来记录该点需不需要经过..)

重在题意不在程序~

注意理解“要经过的所有可能的剧情结束点（按升序输出）。”

就是要你把可能经过的点纪录下来 然后排序输出（不能有重复）

怎么实现大家自己去想

而且如果直接拓扑排序第8个点会有问题

这题规定任务节点1是初始点（即使1也存在入度）

第八组数据是什么!!!

ms图中存在环阿，怎么处理?不是dag了还能求关键路径？

对于关键路径来说，一定有不同的条数，所以，输出的那一条，肯定是随机的……

所以，AC有点靠RP。