blob: b0fd92a85ff5fd219b5dec69b5846f0b2da28112 (
plain)
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
|
# uses Dijkstra's algorithm to find minimal path
# (based on solution for problem 81)
#
# slow, but working
infinity = 99999999
matrix = []
width = 80
height = 80
f = open('082.txt', 'r')
for line in f:
line.rstrip('\n')
line_str = line.split(',')
line_int = [ int(x) for x in line_str ]
matrix.append(line_int)
f.close()
globalmin = 500000
for currentrow in range(height):
# initialize
distance = [infinity] * (width*height)
pre = [None] * (width*height)
distance[currentrow*width] = 0 # start node
Q = range(width*height)
def mindistance(Q):
mini = Q[0]
mind = distance[mini]
for i in Q:
if distance[i] < mind:
mind = distance[i]
mini = i
return mini
def neighbors(u):
n = []
row = u / width
col = u % width
if col == 0:
return[u+1]
if col < width-1:
n.append(row*width + col + 1) # right neighbor
if row < height-1:
n.append((row+1)*width + col) # lower neighbor
if row > 0:
n.append((row-1)*width + col) # upper neighbor
return n
def update(u, v):
alt = distance[u] + matrix[v/width][v%width]
if alt < distance[v]:
distance[v] = alt
pre[v] = u
# main algorithm
while len(Q) > 0:
u = mindistance(Q)
Q.remove(u)
for v in neighbors(u):
if v in Q:
update(u, v)
# search min distance
for targetrow in range(height):
u = targetrow*width-1 # target node
path = [ u ]
while pre[u] != None:
u = pre[u]
path = [u] + path
minsum = 0
for n in path:
minsum += matrix[n/width][n%width]
if minsum < globalmin:
globalmin = minsum
print globalmin
|
