#!/usr/bin/python import sys class Node: def __init__(self,value): self.parentNodes = [] self.childNodes = [] self.weight = 0 self.value = value def calcWeight(self): maxWeight = 0 for node in self.parentNodes: weight = node.weight + node.value if(weight > maxWeight): maxWeight = weight self.weight = maxWeight def __str__(self): return str(self.value) targetNode = None nodeMap = [] def buildNodeMap(nodeMap): for i in range(0,len(nodeMap)): for j in range(0,len(nodeMap[i])): currentNode = nodeMap[i][j] if(i != len(nodeMap)-1): currentNode.childNodes.append(nodeMap[i+1][j]) currentNode.childNodes.append(nodeMap[i+1][j+1]) if(i != 0): if(j == 0): currentNode.parentNodes.append(nodeMap[i-1][j]) elif(j == len(nodeMap[i])-1): currentNode.parentNodes.append(nodeMap[i-1][j-1]) else: currentNode.parentNodes.append(nodeMap[i-1][j]) currentNode.parentNodes.append(nodeMap[i-1][j-1]) def dijkstraReverse(nodeMap): for row in nodeMap: for node in row: node.calcWeight() numRow = 0 for line in sys.stdin: nodeMap.append([]) for elem in line.split(): nodeMap[numRow].append(Node(int(elem))) numRow += 1 buildNodeMap(nodeMap) nodeMap.append([]) targetNode = Node(0) for node in nodeMap[-2]: targetNode.parentNodes.append(node) nodeMap[-1].append(targetNode) dijkstraReverse(nodeMap) print "Result is: " + str(targetNode.weight)