楼下题解 好像和楼下的楼下的楼下的楼下的 除了变量名 其他都一样

我日 一开始没看到‘-1’叫了3次都是80 终于过了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Program P1423;

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

i,j,k,l,m,n:Longint;

t:array[0..200] of longint;

a1,a2,a3:longint;

Begin

Readln(n,m);

for i:=1 to n do

for j:=1 to n do a:=10000000;

for i:=1 to n do read(t[i]);

for i:=1 to m do

begin

read(a1,a2,a3);

if a[a1,a2]>a3+t[a1] then a[a1,a2]:=a3+t[a1];

end;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if ((ik) and (jk)) then

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

begin

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

end;

if a[1,1]10000000 then writeln(a[1,1]) else writeln(-1);

End.

用正向边和反向边分别做一遍spfa

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

好丑的时间虽然又是个Floyd。。

program p1423;

var a:array[1..200,1..200] of longint;

w:array[1..200] of longint;

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

begin

readln(n,m);

for i:=1 to n do

for j:=1 to n do a:=10000000;

for i:=1 to n do readln(w[i]);

for i:=1 to m do

begin readln(p,q,r);

if r+w[q]a+a[k,j] then

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

if a[1,1]=10000000 then a[1,1]:=-1;

writeln(a[1,1]);

end.

弗洛伊德。。。。AC

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

第一次SPFA...boolean搞错了....郁闷....

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一次AC

但题目描述不是很清楚

赤裸裸的FLOYD。 只要把弯道的时间加到边权里就好了。

相当简单

floyd

200*200

有向图FLOYD很好编、

那要是换成无向图、求最短回路、

FLOYD该怎么用、神牛罩我把、

27行。。。

短——————

祝贺上一星半了 50题 感谢

var a,d:array[1..200,1..200] of longint;

w:array[1..200] of longint;

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

begin

readln(n,m);

for i:=1 to n do

for j:=1 to n do

d:=maxint;

for i:=1 to n do readln(w[i]);

for i:=1 to m do

begin

readln(x,y,z);

if a[x,y]0 then

begin

if z+w[y]d+d[k,j] then

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

if d[1,1]=maxint then

write('-1');

if d[1,1]maxint then

write(d[1,1]);

end.

比较水……

-1！！！！！！！！！！

纯粹的floyd，让我大惊失色

注意处理一下输入。接下来超级原版floyd。还是秒杀+一次AC！

汗！

program p1423;

var a,d:array[1..200,1..200] of longint;

w:array[1..200] of longint;

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

begin

readln(n,m);

for i:=1 to n do

for j:=1 to n do

d:=maxint;

for i:=1 to n do readln(w[i]);

for i:=1 to m do

begin

readln(x,y,z);

if a[x,y]0 then

begin

if z+w[y]d+d[k,j] then

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

if d[1,1]=maxint then

write('-1');

if d[1,1]maxint then

write(d[1,1]);

end.

program ll;

var

wq:array[0..300] of longint;

{lt:array[0..100,0..100] of boolean;}

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

v:array[0..300] of boolean;

n,i,x,y,t,j,max:longint;

m,p:longint;

begin

{fillchar(lt,sizeof(lt),false);}

fillchar(a,sizeof(a),0);

readln(n,m);

for i:= 1 to n do

readln(wq[i]);

for i:=1 to m do

begin

readln(x,y,t);

if a[x,y]0 then

if t+wq[y]

SPFA一次就0ms秒杀，可以求出1到2~n点的最小距离d[i]，最后只要输出min(d[i]+a)

{思想：构连通图，DLOYED键环，（题目中说的赛道可多次经过同一条弯道没用），赛道必须经过弯道1又要找最小环,只需找MIN（G[1，I]+G）（G[1，I]+G是一经过弯道1的环）}

{读时去重边，只记录最小边}

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

FLOYD在判重时应该在每次读入边（Z）是加上T（弯道长）然后在MIN{Z，G（I，J）}

否则80分

spfa 终于