blob: f1620e577059ff901c0045636c6a2b825e59e73e (
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
|
# uses Dijkstra's algorithm to find minimal path
# (based on solution for problem 81)
infinity = 999999
matrix = []
width = 80
height = 80
f = open('083.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()
# initialize
distance = [infinity] * (width*height)
pre = [None] * (width*height)
distance[0] = 0
Q = range(width*height)
def mindistance(Q):
mind = infinity
mini = -1
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 < 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
if col > 0:
n.append(row*width + col - 1) # left 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
u = width*height-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]
print minsum
|
