NOIP有N个岛屿，编号为1..N,NOIP决定在岛屿之间发展船运网络。
你在船运票务中心工作，很多人想花尽量少的钱从一个岛到另一个岛进行坐船旅行，他们每个人都报上自己的出发地和目的地，你的任务是告诉他最小花费。但是在这个过程中船的航线不会一直不变，可能会在某个时候增加一些航线，这些新增加的航线显然对之前的询问没有作用，但对之后的询问就要考虑到这些航线了。
按照时间先后的顺序给你一个清单，里面包含询问以及增加航线的信息，写一个程序回答游客提出的问题。
题解：
每加入一条x到y，枚举每一个到x和y的点i和j，比较f[i,x]+f[x,y]+f[y,j]和f[i,j]那个小。
一开始我用弗洛伊德，超时*n
代码：
varn,m:longint;f:array[1..101,1..101] of int64;
procedure init;
vari,j:longint;
beginreadln(n,m);for i:=1 to n dofor j:=1 to n doif i<>j thenf[i,j]:=maxlongint;
end;
procedure main;
vari,j,k,x,y,s:longint;
beginfor i:=1 to m dobeginread(k);if k=0 thenbeginread(x,y);if f[x,y]>=maxlongint thenwriteln(-1)elseif f[x,y]>f[y,x] thenwriteln(f[y,x])elsewriteln(f[x,y]);endelsebeginread(x,y,s);if f[x,y]>s thenbeginf[x,y]:=s;f[y,x]:=s;end;for j:=1 to n dofor k:=1 to n doif f[j,x]+f[x,y]+f[y,k]<f[j,k] thenbeginf[j,k]:=f[j,x]+f[x,y]+f[y,k];f[k,j]:=f[j,k];end;end;end;
end;
begininit;main;
end.
