观光旅游最短路 floyd

题意/Description：

在桑给巴尔岛的Adelton城镇上有一个旅游机构。它们决定在提供许多的其它吸引之外，再向客人们提供旅游本镇的服务。为了从提供的吸引服务中尽可能地获利，这个旅游机构接收了一个精明决定：在相同的起点与终点之间找出一最短路线。

读入/Input：

你的任务是编写一条程序来找类似的的一条路线。在这个镇上，有N个十字路口(编号1至N)，两个十字路口之间可以有多条道路连接，有M条道路（编号为1至M)。但没有一条道路从一个十字路口出发又回到同一个路口。每一条观光路线都是由一些路组成的，这些道路序号是：y1, ..., yk,且k>2。第yi(1<=i<=k-1)号路是连接第xi号十字路口和第x［i+1］号十字路口的；其中第yk号路是连接第xk号十字路口和第x[k+1]号十字路口。而且所有的这些x1,...,xk分别代表不同路口的序号。在某一条观光路线上所有道路的长度的和就是这条观光路线的总长度。换言之L(y1)+L(y2)+...+L(yk)的和, L(yi)就是第yi号观光路线的长度。你的程序必须找出类似的一条路线：长度必须最小，或者说明在这个城镇上不存在这条观光路线。

输出/Output：

每组数据的第一行包含两个正整数：十字路口的个数N(N<=100)，另一个是道路的数目M(M<10000)。接下来的每一行描述一条路：每一行有三个正整数：这条路连接的两个路口的编号，以及这条路的长度（小于500的正整数）。

题解/solution：

可以令e(u,v)表示u和v之间的连边，再令min(u,v)表示，删除u和v之间的连边之后，u和v之间的最短路

最小环则是min(u,v)+ e(u,v)。时间复杂度O（EV2）。

改进算法，在floyd的同时，顺便算出最小环。

一个环中的最大结点为k(编号最大)，与他相连的两个点为i,j，这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中,

所有结点编号都小于k的最短路径长度。

根据floyd的原理，在最外层循环做了k-1次之后，dist[i][j]则代表了i到j的路径中，所有结点编号都小于k的最短路径。

综上所述，该算法一定能找到图中最小环（这个算法还可用于判断负权环）。

代码/Code：

var
  dis,f:array [0..101,0..101] of longint;
  n,m,ans:longint;
procedure init;
var
  i,x,y:longint;
begin
  fillchar(dis,sizeof(dis),$7f div 3);
  fillchar(f,sizeof(f),$7f div 3);
  readln(n,m);
  for i:=1 to m do
    begin
      read(x,y);
      readln(dis[x,y]);
      dis[y,x]:=dis[x,y];
      f[x,y]:=dis[x,y];
      f[y,x]:=f[x,y];
    end;
  ans:=f[0,0];
end;

function min(t,k:longint):longint;
begin
  if t<k then exit(t);
  exit(k);
end;

procedure main;
var
  i,j,k:longint;
begin
  for k:=1 to n do
    begin
      for i:=1 to n do
        for j:=i+1 to n do
          ans:=min(ans,dis[i,j]+f[i,k]+f[k,j]);
      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]);
    end;
  if ans<>f[0,0] then write(ans)
                 else write('No solution');
end;

begin
  init;
  main;
end.

观光旅游 最短路 floyd

观光旅游最短路 floyd