Elaxia的路线
问题描述：
最近，Elaxia 和w**的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，
他们必须合理地安排两个人在一起的时间。Elaxia 和w**每天都要奔波于宿舍和实验室之间，
他们希望在节约时间的前提下，一起走的时间尽可能的长。
现在已知的是Elaxia 和w**所在的宿舍和实验室的编号以及学校的地图：地图上有N
个路口，M 条路，经过每条路都需要一定的时间。
具体地说，就是要求无向图中，两对点间最短路的最长公共路径。
输入格式：
第一行：两个整数N 和M（含义如题目描述）。
第二行：四个整数x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，
1 ≤y2 ≤ N），分别表示Elaxia 的宿舍和实验室及w**的宿舍和实验室的标号（两对点分
别为x1,y1 和x2,y2）。
接下来M 行：每行三个整数，u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000），
表示u 和v 之间有一条路，经过这条路所需要的时间为l。
输出格式：
一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）。
样例输入：
9 10
1 6 7 8
1 2 1
2 5 2
2 3 3
3 4 2
3 9 5
4 5 3
4 6 4
4 7 2
5 8 1
7 9 1
样例输出：
3
数据范围：
对于30%的数据，N ≤ 100；
对于60%的数据，N ≤ 1000；
对于100%的数据，N ≤ 1500，输入数据保证没有重边和自环。
对于x1,x2,y1,y2各做一遍最短路
所有满足(dis[x1,i]+dis[x2,i]=dis[x1,x2])and(dis[y1,i]+dis[y2,i]=dis[y1,y2])的点都在两条最短路的公共路上
然后枚举点对(i,j)
若(abs(dis[x1,i]-dis[x1,j])=abs(dis[x2,i]-dis[x2,j]))and(abs(dis[y1,i]-dis[y1,j])=abs(dis[y2,i]-dis[y2,j]))and(abs(dis[x1,i]-dis[x1,j])=abs(dis[y1,i]-dis[y1,j]))
则abs(dis[x1,i]-dis[x1,j])为一种答案，记录最大的即可
虽然(i,j)可能不在一条最短路上，但若abs(dis[x1,i]-dis[x1,j])相同，则j与i对应的最大点k等价，所以答案不变
错误：对每个点进行了一遍最短路，浪费了时间，没有彻底分析
program travel;
type
arr=array [0..1501] of longint;
var
ans,tot,n,m,i,j,k,x1,y1,x2,y2,u,v,l:longint;
dl,heap,rank:array [0..30001] of longint;
root:array [0..1501] of longint;
next,point,cost:array [0..3000001] of longint;
dis:array [0..1501] of arr;
procedure swap (var a,b:longint);
var
i:longint;
begin
i:=a;
a:=b;
b:=i;
end;
procedure insert (now:longint;var dis:arr);
var
i:longint;
begin
inc(tot);
heap[tot]:=now;
rank[now]:=tot;
i:=tot;
while (i>1)and(dis[heap[i]]<dis[heap[i div 2]]) do
begin
swap(heap[i],heap[i div 2]);
swap(rank[heap[i]],rank[heap[i div 2]]);
i:=i div 2;
end;
end;
procedure delete (now:longint;var dis:arr);
var
i:longint;
begin
if rank[now]=tot then
begin
heap[rank[now]]:=0;
rank[now]:=0;
dec(tot);
exit;
end;
i:=rank[now];
swap(heap[rank[now]],heap[tot]);
swap(rank[heap[rank[now]]],rank[heap[tot]]);
rank[heap[tot]]:=0;
heap[tot]:=0;
dec(tot);
if (i>1)and(dis[heap[i]]<dis[heap[i div 2]]) then
while (i>1)and(dis[heap[i]]<dis[heap[i div 2]]) do
begin
swap(heap[i],heap[i div 2]);
swap(rank[heap[i]],rank[heap[i div 2]]);
i:=i div 2;
end
else
while (dis[heap[i*2]]<dis[heap[i]])or(dis[heap[i*2+1]]<dis[heap[i]]) do
if dis[heap[i*2]]<dis[heap[i*2+1]] then
begin
swap(heap[i],heap[i*2]);
swap(rank[heap[i]],rank[heap[i*2]]);
i:=i*2;
end
else
begin
swap(heap[i],heap[i*2+1]);
swap(rank[heap[i]],rank[heap[i*2+1]]);
i:=i*2+1;
end;
end;
procedure connect(u,v,l:longint);
begin
inc(tot);
point[tot]:=v;
cost[tot]:=l;
next[tot]:=root[u];
root[u]:=tot;
end;
procedure spfa (now:longint);
var
i,j,k:longint;
begin
for i:=1 to tot do
heap[i]:=0;
fillchar(rank,sizeof(rank),0);
tot:=0;
dis[now,now]:=0;
insert(now,dis[now]);
while tot>0 do
begin
j:=heap[1];
delete(heap[1],dis[now]);
k:=root[j];
while k<>0 do
begin
if (dis[now][j]+cost[k]<dis[now][point[k]]) then
begin
if rank[point[k]]<>0 then delete(point[k],dis[now]);
dis[now][point[k]]:=dis[now][j]+cost[k];
insert(point[k],dis[now]);
end;
k:=next[k];
end;
end;
end;
begin
assign(input,'travel.in');
reset(input);
assign(output,'travel.out');
rewrite(output);
read(n,m);
read(x1,x2,y1,y2);
for i:=1 to m do
begin
if i=1500 then
begin
j:=1;
end;
read(u,v,l);
connect(u,v,l);
connect(v,u,l);
end;
tot:=0;
fillchar(dis,sizeof(dis),63);
spfa(x1);
spfa(x2);
spfa(y1);
spfa(y2);
tot:=0;
for i:=1 to n do
if (dis[x1,i]+dis[x2,i]=dis[x1,x2])and(dis[y1,i]+dis[y2,i]=dis[y1,y2]) then
begin
inc(tot);
dl[tot]:=i;
end;
ans:=0;
for i:=1 to tot do
for j:=1 to tot do
if (abs(dis[x1,dl[i]]-dis[x1,dl[j]])=abs(dis[x2,dl[i]]-dis[x2,dl[j]]))
and(abs(dis[y1,dl[i]]-dis[y1,dl[j]])=abs(dis[y2,dl[i]]-dis[y2,dl[j]]))
and(abs(dis[x1,dl[i]]-dis[x1,dl[j]])=abs(dis[y2,dl[i]]-dis[y2,dl[j]])) then
if ans<abs(dis[y2,dl[i]]-dis[y2,dl[j]]) then ans:=abs(dis[y2,dl[i]]-dis[y2,dl[j]]);
writeln(ans);
close(input);
close(output);
end.