1 files changed, 76 insertions, 0 deletions
diff --git a/083.py b/083.py
new file mode 100644
index 0000000..f1620e5
--- /dev/null
+++ b/083.py
@@ -0,0 +1,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
+