結果

問題 No.20 砂漠のオアシス
ユーザー yuma25689yuma25689
提出日時 2015-10-31 03:16:56
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 3,957 bytes
コンパイル時間 745 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 28,032 KB
最終ジャッジ日時 2024-04-21 06:46:45
合計ジャッジ時間 6,973 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
11,008 KB
testcase_01 AC 29 ms
11,008 KB
testcase_02 AC 31 ms
11,008 KB
testcase_03 AC 67 ms
11,648 KB
testcase_04 AC 66 ms
11,776 KB
testcase_05 TLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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<edgeCount and 0<=to_y<edgeCount:
				toNodeInduces.append( to_y + edgeCount*to_x )
		nodes.append( Node(x,y,INF,damageOfPos[x][y],toNodeInduces) )

# 最初の点のコストを0に初期化
nodes[0].minFromCost=0

oasisIndex=-1

if not ( oasisPos[0]==0 and oasisPos[1]==0 ):
	oasisIndex=oasisPos[1]-1 + edgeCount*(oasisPos[0]-1)

# 最初のnodeからdijkstra法
targets=[]
targets.append(nodes[oasisIndex])
targets.append(nodes[len(nodes)-1])
updateCostByDijkstra(nodes[0],nodes,targets)

# for node in nodes:
# 	print( "[" + str(node.x) + "," + str(node.y) + "]="+str(node.minFromCost) )

if nodes[len(nodes)-1].minFromCost < HP:
	print('YES')
	sys.exit(0)

# HPが足りなかった
# print('HP{0} not enouph.cost{1}'.format( HP, nodes[len(nodes)-1].minFromCost) )

# オアシス経由でいけるか試す
if oasisPos[0]==0 and oasisPos[1]==0:
	# print('not exist oasis')
	print('NO')
	sys.exit(0)


# print('oasis exists [toCost]={}'.format( nodes[oasisIndex].minFromCost ) )

if nodes[oasisIndex].minFromCost < HP:
	HP = (HP-nodes[oasisIndex].minFromCost)*2
else:
	# print('cant reach oasis{} HP{}'.format( nodes[oasisIndex].minFromCost, HP))
	print('NO')
	sys.exit(0)

# print('HP recovery to {}'.format(HP))

# 最初の点をoasisにしてもう一度dijkstra
for node in nodes:
	node.clear()
nodes[oasisIndex].minFromCost=0
updateCostByDijkstra(nodes[oasisIndex],nodes,[nodes[len(nodes)-1]])

# for node in nodes:
# 	print( "[" + str(node.x) + "," + str(node.y) + "]="+str(node.minFromCost) )

if nodes[len(nodes)-1].minFromCost < HP:
	print('YES')
else:
	print('NO')
0