Граф. Для каждой пары городов найти длину кратчайшего пути между ними.

uses crt;
const maxn=100;
var a:array[1..maxn,1..maxn]of integer; //матрица смежности
 
w:array[1..maxn,1..maxn]of integer; //таблица кратчайших путей
 
i,j,N:integer;
input:text;
 
function min(a,b:longint):longint;
begin
 if a<b then min:=a else min:=b;
end;
 
procedure floyd;
var i,j,k:integer;
begin
 for i:=1 to n do for j:=1 to n do w[i,j]:=a[i,j];
 for k:=1 to n do
  for i:=1 to n do 
   for j:=1 to n do W[i,j] := min(W[i,j], W[i,k] + W[k,j]);
end;
 
begin
 clrscr;
 assign(input,'input.txt');
 reset(input);
 readln(input, N);
 for i:=1 to N do
 begin
    for j:=1 to N do read(input,a[i,j]);
    readln(input);
 end;
 close(input);
 floyd;
 writeln('Таблица расстояний');
 for i:=1 to N do
 begin
  for j:=1 to N do write(W[i,j],' ');
  writeln;
 end;
 readln;
end.

const
  maxn = 100;
  inf = 100000000000;
 
var
  a: array[1..maxn, 1..maxn] of integer; //матрица смежности
  
  w: array[1..maxn, 1..maxn] of integer; //таблица кратчайших путей
  
  i, j, N: integer;
  input: text;
 
procedure Deisktr;
var
  i, j, v, s, min: longint;
  visited: array[1..MaxN] of boolean;
  d: array[1..maxn] of longint;
 
begin
  visited[s] := TRUE; 
  for i := 1 to N do D[i] := A[s, i]; 
  for i := 1 to n - 1 do 
  begin
    min := inf;
    for j := 1 to N do 
      if (not visited[j]) and (D[j] < min) then
      begin
        min := D[j]; 
        v := j; 
      end;
    for j := 1 to N do if (D[j] > D[v] + A[v, j]) and (D[v] < inf) and (A[v, j] < inf) then D[j] := D[v] + A[v, j]; 
    s := v; 
    visited[v] := TRUE;
  end;
end;
 
begin
  assign(input, 'input.txt');
  reset(input);
  readln(input, N);
  for i := 1 to N do
  begin
    for j := 1 to N do read(input, a[i, j]);
    readln(input);
  end;
  close(input);
  deisktr;
  writeln('Таблица расстояний');
  for i := 1 to N do
  begin
    for j := 1 to N do write(W[i, j], ' ');
    writeln;
  end;
  readln;
end.