【题意】
给定一个有向加权图，求s到f的最短路径和比最短路径长1的路径数
【输入】
多组数据，第一行一个数字t表示有多少组数据
每组数据第一行两个数n、m表示点的个数和边的个数(n<=1000,m<=10000)
接下来m行每行三个整数a、b、l表示存在一条长度为l连接a、b的有向边
最后一行两个整数s、f
【输出】
对于每组数据输出一行，该行一个整数表示路径数
heap+dijkstra
如果用A*的话会超时，因为最终答案是10^8等级的
每个点维护两个值，最小值和次小值，再加上计数即可，代码略显臃肿
program poj3463;
var
ans,tot,n,m,i,j,k,t,s,f,a,b,l:longint;
root:array [0..10001] of longint;
rank,count,dis:array [0..1,0..10001] of longint;
next,point,cost:array [0..100001] of longint;
heap,mode:array [0..20001] of longint;
procedure swap (var a,b:longint);
var
i:longint;
begin
i:=a;
a:=b;
b:=i;
end;
procedure connect (a,b,l:longint);
begin
inc(tot);
point[tot]:=b;
cost[tot]:=l;
next[tot]:=root[a];
root[a]:=tot;
end;
procedure insert (o,now:longint);
var
i:longint;
begin
inc(tot);
heap[tot]:=now;
mode[tot]:=o;
rank[o,now]:=tot;
i:=tot;
while (i>1)and(dis[mode[i div 2],heap[i div 2]]>dis[o,now]) do
begin
swap(rank[mode[i div 2],heap[i div 2]],rank[o,now]);
swap(mode[i div 2],mode[i]);
swap(heap[i div 2],heap[i]);
i:=i div 2;
end;
end;
procedure delete (o,now:longint);
var
i:longint;
begin
if rank[o,now]=0 then exit;
if rank[o,now]=tot then
begin
heap[tot]:=0;
mode[tot]:=0;
rank[o,now]:=0;
dec(tot);
exit;
end;
i:=rank[o,now];
swap(rank[o,now],rank[mode[tot],heap[tot]]);
swap(heap[i],heap[tot]);
swap(mode[i],mode[tot]);
rank[o,now]:=0;
heap[tot]:=0;
mode[tot]:=0;
dec(tot);
if (i>1)and(dis[mode[i div 2],heap[i div 2]]>dis[mode[i],heap[i]]) then
while (i>1)and(dis[mode[i div 2],heap[i div 2]]>dis[mode[i],heap[i]]) do
begin
swap(rank[mode[i div 2],heap[i div 2]],rank[mode[i],heap[i]]);
swap(mode[i],mode[i div 2]);
swap(heap[i],heap[i div 2]);
i:=i div 2;
end
else
while (dis[mode[i*2],heap[i*2]]<dis[mode[i],heap[i]])or
(dis[mode[i*2+1],heap[i*2+1]]<dis[mode[i],heap[i]]) do
if dis[mode[i*2],heap[i*2]]<dis[mode[i*2+1],heap[i*2+1]] then
begin
swap(rank[mode[i * 2],heap[i * 2]],rank[mode[i],heap[i]]);
swap(mode[i],mode[i * 2]);
swap(heap[i],heap[i * 2]);
i:=i * 2;
end
else
begin
swap(rank[mode[i * 2 + 1],heap[i * 2 + 1]],rank[mode[i],heap[i]]);
swap(mode[i],mode[i * 2 + 1]);
swap(heap[i],heap[i * 2 + 1]);
i:=i * 2 + 1;
end
end;
procedure spfa;
var
who,now,i,j,k:longint;
begin
while tot>0 do
begin
who:=heap[1];
now:=mode[1];
delete(now,who);
k:=root[who];
while k<>0 do
begin
if dis[now,who]+cost[k]<dis[0,point[k]] then
begin
swap(dis[0,point[k]],dis[1,point[k]]);
count[1,point[k]]:=count[0,point[k]];
dis[0,point[k]]:=dis[now,who]+cost[k];
count[0,point[k]]:=count[now,who];
delete(0,point[k]);
delete(1,point[k]);
insert(0,point[k]);
insert(1,point[k]);
end
else
if dis[now,who]+cost[k]=dis[0,point[k]] then
count[0,point[k]]:=count[0,point[k]]+count[now,who]
else
if dis[now,who]+cost[k]<dis[1,point[k]] then
begin
dis[1,point[k]]:=dis[now,who]+cost[k];
count[1,point[k]]:=count[now,who];
delete(1,point[k]);
insert(1,point[k]);
end
else
if dis[now,who]+cost[k]=dis[1,point[k]] then
count[1,point[k]]:=count[1,point[k]]+count[now,who];
k:=next[k];
end;
end;
end;
begin
read(t);
while t>0 do
begin
fillchar(root,sizeof(root),0);
fillchar(heap,sizeof(heap),0);
fillchar(mode,sizeof(mode),0);
fillchar(dis,sizeof(dis),63);
fillchar(count,sizeof(count),0);
tot:=0;
read(n,m);
for i:=1 to m do
begin
read(a,b,l);
connect(a,b,l);
end;
read(s,f);
tot:=0;
dis[0,s]:=0;
count[0,s]:=1;
insert(0,s);
spfa;
ans:=count[0,f];
if dis[0,f]+1=dis[1,f] then ans:=ans+count[1,f];
writeln(ans);
dec(t);
end;
end.