jzoj 1415. 【2012.04.14普及组】最短距离

lzusa 发布于 2019-03-23 1554 次阅读

题目描述

有N个城市，任何两个城市之间都有一条道路连接，求任意两城市之间的最短距离.例如:6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为7。
城市1 城市2 城市3 城市4 城市5 城市6
城市1 0 2 3 1 12 15
城市2 2 0 2 5 3 12
城市3 3 2 0 3 6 5
城市4 1 5 3 0 7 9
城市5 12 3 6 7 0 2
城市6 15 12 5 9 2 0

注意题目中的边为有向边，可能会出现A到B的距离不等于B到A的距离。

输入

输入文件shortest.in,第一行一个数N,其中2 < N<=600
接下来2到N+1行数据,每行N个数,每个数0<=M<2000.
最后一行,即第N+2行,两个数A,B,即求从A城市到B城市的最短距离 。

输出

输出文件shortest.out,一行,A到B的最短距离。

思路

就是普通的最短路问题我用了Floyd，竟然没有超时。。。。

var
  f:array[0..1000,0..1000] of longint;
  i,j,k,n,m,s,x,y:longint;
  a:array[0..100000] of longint;  
begin
assign(input,'shortest.in'); reset(input);
assign(output,'shortest.out');rewrite(output);
  readln(n);
  for i:=1 to n do
  begin
    for j:=1 to n do
      read(f[i,j]);
    readln;
  end;
  readln(x,y);
  for k:=1 to n do
    for i:=1 to n do  
      for j:=1 to n do
        if (i<>k) and (i<>j) and (k<>j) and (f[i,k]+f[k,j]
]]>