给一个有向图，顶点数少于50，有Q条询问（Q<=100000），对于每条询问（x1 y1），输出他们之间的最小密度路径的密度（长度比边数）

两种实践方法，一个是FLOYD，再就是二维SPFA，注意数据有环，SPFA时要控制边数少于n才行，至于为什么，是困扰几代人的烦恼了。

d[i,j,k]表示从i到j走过k条路径的最小路径长度

floyd

1 program path(input,output);  2 var  3   i,j,k,l,m,n,w,p,x,y:longint;  4   max,tmp:real;  5   f:array[0..51,0..51,0..51]  of longint;  6 begin  7   assign(input,'path.in');  8   reset(input);  9   assign(output,'path.out'); 10   rewrite(output); 11   readln(n,m); 12   fillchar(f,sizeof(f),255); 13   for i:=1 to m do 14     begin 15       readln(x,y,w); 16       if (f[x,y,1]=-1) or (f[x,y,1]>w) then 17       f[x,y,1]:=w; 18     end; 19   for i:=1 to n do f[i,i,0]:=0; 20   for l:=2 to n do 21     for k:=1 to n do 22       for i:=1 to n do 23         for j:=1 to n do 24           if (f[i,k,l-1]>-1)  and (f[k,j,1]>-1) and 25             ((f[i,j,l]=-1) or (f[i,k,l-1]+f[k,j,1]
      
       -1) and (f[x,y,i]
       
        100110001  then writeln(max:0:3) 35        else writeln('OMG!'); 36     end; 37   close(input); 38   close(output); 39 end.
       
      

SPFA

1 program path(input,output);   2 type   3    node     = ^link;   4    link     = record   5           goal,w : longint;   6           next   : node;   7        end;           8    node2 = record   9           now  : integer;  10           step : longint;  11        end;        12 var  13    l      : array[0..100] of node;  14    v      : array[0..60,0..2010] of boolean;  15    d      : array[0..60,0..60,0..2010] of longint;  16    g      : array[0..60,0..60] of boolean;  17    q      : array[0..100010] of node2;  18    answer : array[0..60,0..60] of double;  19    n,m,qq : longint;  20 procedure add(xx,yy,ww: longint );  21 var  22    tt : node;  23 begin  24    new(tt);  25    tt^.w:=ww;  26    tt^.goal:=yy;  27    tt^.next:=l[xx];  28    l[xx]:=tt;  29 end; {
      add }  30 procedure init;  31 var  32    i,j,k,xxx,yyy,www : longint;  33 begin  34    readln(n,m);  35    for i:=1 to n do  36       l[i]:=nil;  37    for i:=1 to n do  38       for j:=1 to n do  39      for k:=1 to m do  40         d[i,j,k]:=maxlongint>>2;  41    for i:=1 to n do  42       for j:=1 to n do  43      if i=j then  44         answer[i,j]:=0  45      else  46         answer[i,j]:=-1;  47    fillchar(g,sizeof(g),false);  48    for i:=1 to m do  49    begin  50       readln(xxx,yyy,www);  51       add(xxx,yyy,www);  52       g[xxx,yyy]:=true;  53    end;  54    for k:=1 to n do  55       for i:=1 to n do  56      for j:=1 to n do  57         g[i,j]:=g[i,j] or (g[i,k] and g[k,j]);  58 end; {
      init }  59 procedure spfa(vo :longint );  60 var  61    head,tail : longint;  62    t         : node;  63 begin  64    fillchar(v,sizeof(v),false);  65    head:=0;  66    tail:=1;  67    d[vo,vo,0]:=0;  68    v[vo,0]:=true;  69    q[1].step:=0;  70    q[1].now:=vo;  71    while head
      
       nil do  79       begin  80      if d[vo,q[head].now,q[head].step]+t^.w
       
        =0 then 111       begin 112      writeln(answer[x1,y1]:0:3); 113      continue; 114       end; 115       answer[x1,y1]:=999999999; 116       for j:=1 to m do 117      if d[x1,y1,j]<(maxlongint>>2) then 118         if (d[x1,y1,j]/j)