task-solutions/Dijkstra.pas at master · boriswinner/task-solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
program project1;
const inf = 10000000;
type
  spisok=record
    apex: array of integer; //вершина графа, до которой идёт путь
    path2apex: array of integer; //расстояние до этой вершины графа
  end;
var
  graph1: array [1..1000] of spisok;
  d: array [1..1000] of integer;
  z: array [1..1000] of integer;
  Y: array [1..1000] of boolean; //множество посещённых вершин
  N,M,S,i,j,u,minmetka,v: integer;
  {
  i,j,z - рабочие переменные
  N - множество вершин графа
  M - количество рёбер
  S - вершина a (начальная вершина)
  d[u] - по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u
  }
  f1,f2: text;
begin
  //инициализация
  assign (f1, 'input.txt');
  assign (f2, 'output.txt');


  //чтение
  reset (f1);
  read (f1, N);
  read (f1, M);
  readln (f1, S);

  for i := 1 to M do
  begin
    read (f1, j); //читаем номер вершины старта
    inc (z[j]);
    setlength(graph1[j].apex, z[j] + 1);
    read (f1, graph1[j].apex[z[j]]); //читаем номер вершины конца
    setlength(graph1[j].path2apex, z[j] + 1);
    readln (f1, graph1[j].path2apex[z[j]]); //читаем длину ребра
  end;
  close (f1);

  for i := 1 to N do
    if (i <> S) then
       d[i] := inf;


  for i := 1 to N do
  begin
    minmetka := inf;
    for j := 1 to N do
      if (not Y[j]) and (d[j] <= minmetka) then
        begin
          v := j;
          minmetka := d[j];
        end;

    for j := 1 to z[v] do
       if (d[v]+graph1[v].path2apex[j]<d[graph1[v].apex[j]]) THEN
         d[graph1[v].apex[j]] := d[v]+graph1[v].path2apex[j];
    Y[v] := TRUE;
  end;

  rewrite (f2);
  for i := 1 to N do
    begin
      if (d[i] <> inf) THEN
        write (f2,d[i])
      else
        write (f2,'-1');
      write (f2,' ');
    end;
  close (f2);
end.