var q,n,m,i,j,k,l,a,b,c:longint;
f,t:array[0..100,0..100] of qword;
begin
read(n,m);
for i:=1 to n do
for j:=1 to n do begin
f[i,j]:=maxlongint;
if i=j then f[i,j]:=0;
end;
for l:=1 to m do begin
read(q);
if q=1 then begin
read(a,b,c);
if c<f[a,b] then begin f[a,b]:=c;f[b,a]:=c;end;
end
else begin
read(a,b);t:=f;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if t[i,k]+t[k,j]<t[i,j] then
t[i,j]:=t[i,k]+t[k,j];
if t[a,b]<maxint then writeln(t[a,b])
else writeln('-1');
end;
end;
end.
为什么只有20分啊，错误在哪里
4 条评论
-
正在加载...99% LV 8 @ 2016-03-22 21:45:30
请看“if t[a,b]<maxint then writeln(t[a,b])”！
数据肯定会出超过maxint(32767)的数据的！
下面是60的Floyed：
var
i,j,k,m,n,s,t,u,v,e:longint;
a:array[0..101,0..101]of longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x) else exit(y);
end;
function dijs(x,y:longint):longint;
var
i,j,k:longint;
dis:array[0..101,0..101]of longint;
begin
dis:=a;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
dis[i,j]:=min(dis[i,j],dis[i,k]+dis[k,j]);
if dis[x,y]=maxlongint div 3 then exit(-1) else exit(dis[x,y]);
end;
begin
for i:=0 to 101 do
for j:=0 to 101 do
a[i,j]:=maxlongint div 3;
readln(n,m);
for i:=1 to m do
begin
read(k);
if k=1 then
begin
readln(u,v,e);
if (e>a[u,v])and(a[u,v]<>-1) then continue;
a[u,v]:=e;a[v,u]:=e;
end
else
begin
readln(s,t);
writeln(dijs(s,t));
end;
end;
end. -
@ 2015-06-07 10:01:45
spfa才是王道
-
@ 2015-05-24 00:49:29
floyd太渣，用spfa吧
-
@ 2015-05-22 23:26:03
呃……Floyd的效率不够吧…
-
@ 2016-03-22 21:41:46
Floyed可以得60的
-
- 1
