-
Notifications
You must be signed in to change notification settings - Fork 0
/
Project3.dpr
104 lines (89 loc) · 2.44 KB
/
Project3.dpr
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
program Project3;
{$APPTYPE CONSOLE}
uses
SysUtils, Diagnostics;
const
maxnodes = 5000;
inf = 65536;
type
intArray = array [0..maxnodes] of integer;
var
nodes : integer;
connArray : array [1..maxnodes, 0..maxnodes] of integer; //described original connection
distanceArray : array [0..maxnodes, 0..maxnodes] of integer;
src, dest : integer;
//map [x, 0] is count of element, just like string
map : array [0..inf] of intArray;
stopwatch: TStopwatch;
function STP(src, dest : integer) : integer;
var
loc : integer;
distanceList : array [1..maxnodes] of integer;
i, j : integer;
target : integer;
begin
for i:=1 to nodes do distanceList[i]:=inf;
distanceList[src]:=0;
{
initialisation
}
for i:=1 to nodes do
if (distanceArray[src, i]<inf) and (distanceArray[src, i]>0) then
begin
target:=distanceArray[src, i];
inc(map[target, 0]);
map[target, map[target, 0]]:=i;
distanceList[i]:=target;
end;
{
actual process time
}
loc:=0;
repeat
for i:=1 to map[loc, 0] do
for j:=1 to connArray[map[loc, i], 0] do
begin
target:=loc+distanceArray[map[loc, i], connArray[map[loc, i], j]];
if (distanceList[connArray[map[loc, i], j]]>target) then
begin
inc(map[target, 0]);
map[target, map[target, 0]]:=connArray[map[loc, i], j];
distanceList[connArray[map[loc, i], j]]:=target
end;
end;
inc(loc);
until distanceList[dest]<=loc;
writeln(loc);
STP:=distanceList[dest];
end;
var
i, j : integer;
begin
stopwatch:=TStopWatch.StartNew;
AssignFile(input, 'input.txt');
reset(input);
read(nodes);
read(src, dest);
for i:=1 to nodes do
begin
for j:=1 to nodes do
begin
read(distanceArray[i, j]);
if (distanceArray[i, j]<inf) then
begin
inc(connArray[i, 0]); //increment the no of connected node
connArray[i, connArray[i, 0]]:=j; //enter the connected node
end;
end;
end;
close(input);
writeln('input reading time: ', stopwatch.ElapsedMilliseconds);
stopwatch.Reset;
stopwatch.Start;
writeln(STP(src, dest));
writeln('process time: ', stopwatch.ElapsedMilliseconds);
// writeln('Shortest Path : ', distanceArray[src, dest]);
AssignFile(input, '');
readln;
{ TODO -oUser -cConsole Main : Insert code here }
end.