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,targetNodes=None): ''' firstNodeからのnodeList内の全ノードに対して移動するのにかかるコストを取得 ただし、dijkstra法なので、0<=cost ''' queue=[] heapq.heapify(queue) heapq.heappush( queue, firstNode ) getTarget=False while 0 < len(queue): # キューが空でない限り # キュー取り出し doneNode=heapq.heappop(queue) doneNode.done=True if targetNodes: getTarget=True for t in targetNodes: if not t.done: getTarget=False break if getTarget: return for i in doneNode.to: if nodeList[i].done==True: continue # 接続先ノードを更新 current = doneNode.minFromCost + nodeList[i].toCost if nodeList[i].minFromCost == INF or current < nodeList[i].minFromCost: nodeList[i].minFromCost = current if nodeList[i] not in queue: # 参照渡しの必要あり。pythonではそれで普通かな? heapq.heappush( queue, nodeList[i] ) # print( "[" + str(doneNode.x) + "," + str(doneNode.y) + "]" + "->[" + str(nodeList[i].x) + "," + str(nodeList[i].y) \ # + "]"+"="+str(nodeList[i].minFromCost) + "(" + str(nodeList[i].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