/
ch-2.lua
69 lines (56 loc) · 1.37 KB
/
ch-2.lua
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
#!/opt/local/bin/lua
--
-- See ../README.md
--
--
-- Run as: lua ch-2.lua < input-file
--
function shortest_path (matrix, from, to, exclude)
if (1 + #exclude == #matrix) then
return matrix [from] [to], {to}
end
local shortest = 10 ^ 999 -- Should be big enough...
local sh_path = {}
local new_exclude = {}
for k, v in pairs (exclude) do
new_exclude [k] = v
end
new_exclude [from] = 1
local next
for next = 1, #matrix do
if next == from or next == to or new_exclude [next] == 1 then
goto end_loop
end
local length
local path
length, path = shortest_path (matrix, next, to, new_exclude)
if shortest > length + matrix [from] [next] then
shortest = length + matrix [from] [next]
sh_path = {}
sh_path [1] = next
for k, v in pairs (path) do
sh_path [k + 1] = v
end
end
::end_loop::
end
return shortest, sh_path
end
matrix = {}
for line in io . lines () do
row = {}
for d in line : gmatch ("%d+") do
table . insert (row, d)
end
table . insert (matrix, row)
end
local length
local path
length, path = shortest_path (matrix, 1, 1, {})
print (length)
io . write ("0")
for i = 1, #path do
io . write (" ")
io . write (path [i] - 1)
end
print ("")