import sys import heapq INF=1e10 class Node: ''' このdijkstra法で使用するnode ''' def __init__(self,x,y,fc,tc,to): self.x=x self.y=y self.minFromCost=fc self.toCost=tc self.to=to self.done=False def __eq__(self,n): return self.x == n.x and self.y == n.y def __lt__(self,n): return self.minFromCost < n.minFromCost def clear(self): self.minFromCost=INF self.done=False def updateCostByDijkstra(firstNode,nodeList): ''' firstNodeからのnodeList内の全ノードに対して移動するのにかかるコストを取得 ただし、dijkstra法なので、0<=cost ''' queue=[] heapq.heapify(queue) heapq.heappush( queue, firstNode ) minFromCost=0 while 0 < len(queue): # キューが空でない限り # キュー取り出し doneNode=heapq.heappop(queue) doneNode.done=True for i in doneNode.to: node=nodeList[i] # 接続先ノードを更新 current = doneNode.minFromCost + node.toCost if node.minFromCost == INF or current < node.minFromCost: node.minFromCost = current if node not in queue: # 参照渡しの必要あり。pythonではそれで普通かな? heapq.heappush( queue, node ) #print( "[" + str(doneNode.x) + "," + str(doneNode.y) + "]" + "->[" + str(node.x) + "," + str(node.y) \ # + "]"+"="+str(node.minFromCost) + "(" + str(node.toCost) +")") line=sys.stdin.readline() line1=line.split() edgeCount = int(line1[0]) HP=int(line1[1]) oasisPos=[int(line1[2]),int(line1[3])] damageOfPos=[[0 for i in range(edgeCount)] for j in range(edgeCount)] # 各点から目的地までの最小コスト for y in range(edgeCount): line=sys.stdin.readline() lineN=line.split() for x in range(edgeCount): damageOfPos[x][y]=int(lineN[x]) # Dijkstra #minFromCost=[[INF for i in range(edgeCount)]for j in range(edgeCount)] NextCoords=[(1,0),(0,1),(-1,0),(0,-1)] # nodeを作成 # 接続先情報も上下左右として作成する nodes=[] for x in range(edgeCount): for y in range(edgeCount): toNodeInduces=[] for i in range(len(NextCoords)): (dx,dy)=NextCoords[i] to_x=x+dx to_y=y+dy if 0 <=to_x