lx '然后，“要经过的所有可能的剧情结束点”，也许会有人把所有最长路径全输出呢。 ' 原来说的就是我啊.....可是错误答案为什么提示的是：‘输出数据比标准答案长’？？？！！！！....speechless...

标准的AOE网

K A O!

第8个点死活过不了

囧，用spfa 1、5 WA

还是用floyd 吧

spfa 1、5 WA的原因是最长路不止一条吧

顺便喷下出题人，我还以为是最短路……

这题其实挺好的，只是描述有点多，大家看得都乱了吧？

“为了体验游戏的完整性，小呆决定要看到所有的分支剧情——完成所有的任务。”

就是说 1->n+1 同时发出多条路径，经过所有的点。

因为是同时的，所以最短时间就是所有路径中所花时间最多的，即求最长路。

样例就是

4

5

1 2 2

2 3 2

3 5 3

1 4 3

4 5 3

(1)--2-->(2)--2-->(3)--3-->(5)

│ ︿

│ │

└--3-->(4)---|---|3---|---|---|---|---|-┘

完成所有任务就是，同时走两条路径。

(1)--2-->(2)--2-->(3)--3-->(5) 费时7

(1)--3-->(4)--3-->(5) 费时6

总共最小费时7

Floyd即可。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1027;

var a,v:array[0..101,0..101] of longint;

i,j,k,l,m,n,p,q,r:longint;

begin

readln(n);readln(m);inc(n);

for i:=1 to m do begin

readln(p,q,r); a[p,q]:=r; end;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if (a=0) or (a[k,j]=0) or (i=j) or (j=k) or (i=k) then continue

else

if a+a[k,j]>a then

a:=a+a[k,j];

writeln(a[1,n]);

for i:=1 to n do

if a[1,i]+a=a[1,n] then

write(i,' ');writeln;

end.

传说中的弗洛伊德

　　　3　　　　5

　　/　\　　　/　\

　/　　　\　/　　　\

①　　　　②　　　　③

　\　　　/　\　　　/

　　\　/　　　\　/

　　　4　　　　4

这个图的是8还是9？

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

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

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

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

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

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

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

程序：

http://lifeich1.spaces.live.com/blog/cns!9AB465A9D807BE22!168.entry

额，我觉得楼下那位，自己理解题目错了而已。

挺好理解的啊= =||

强烈BS此题。

首先，本题很容易让人误解为最短路径，其实是最长路径。

其次，“为了体验游戏的完整性，小呆决定要看到所有的分支剧情——完成所有的任务” 这句话，很多人会认为是拓扑排序；

然后，“要经过的所有可能的剧情结束点”，也许会有人把所有最长路径全输出呢。

以后这种太让人看不懂的题尽量少出，免得害人。

SPFA，0ms AC

这么水的题，21行的程序，怎么通过率只有16%？

二十四行程序；

数据很小，用floyd求两点间的最长路径。

如果w[1,k]+w[k,n+1]=f[1,n]的话，就输出这个k

0ms

这绝对是一道破题

“为了体验游戏的完整性，小呆决定要看到所有的分支剧情——完成所有的任务”

谁知道这句是说 经过最多的点 还是 最长的时间

还有 这是朦胧作品么？

“你要告诉小呆完成整个游戏至少需要多少时间以及要经过的所有可能的剧情结束点（按升序输出）。”

谁知道这是一条路径的 还是 有相同长度路径 经过的点都算

总之 破题

多谢各位的题解 不看就没办法做出来了

再次提倡Floyd 相当好做

评测机。。。

同样的程序提交了3次。。。

rp真低。。

var n,m,x,y,z,i,j,k:longint;

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

begin

read(n,m);

for i:=1 to m do

begin

read(x,y,z);

a[x,y]:=z;

end;

for i:=1 to n+1 do

for j:=1 to n+1 do

for k:=1 to n+1 do

if (ij) and (ik) and (jk) and (a0) and (a[k,j]0) then

if a

留下纪念。。200次递交。。AC

.

直接dfs即可。。（注意多条最长路的时候也要把点记下来。）

或者。。

Floyd真的也很妙。。（我没试。。）

if f[1,k]+f[k,n+1]=f[1,n+1] then

把k点加入到输出序列。。（k点在最长路上）。

Floyed+DFS=0ms。

注意：1、题目要求最长路及其路径；

2、有多条最长路的情况；

3、每个点只能走一次。

破题，理论上不应该有环，不然那游戏该怎么玩

FFFF

var

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

n,m:longint;

procedure work;

var i,j,k:longint;

begin

for i:=1 to n+1 do

for j:=1 to n+1 do

if ij then

for k:=1 to n do

if (ik)and(jk) then

if (a0)and(a[k,j]0) then

if (a

Floyed秒杀!!