結果

問題 No.1 道のショートカット
ユーザー yuma25689yuma25689
提出日時 2015-11-04 15:33:34
言語 Python3
(3.11.6 + numpy 1.26.0 + scipy 1.11.3)
結果
AC  
実行時間 103 ms / 5,000 ms
コード長 3,933 bytes
コンパイル時間 122 ms
コンパイル使用メモリ 11,052 KB
実行使用メモリ 9,260 KB
最終ジャッジ日時 2023-09-27 21:48:55
合計ジャッジ時間 2,822 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 15 ms
7,892 KB
testcase_01 AC 14 ms
8,296 KB
testcase_02 AC 15 ms
8,184 KB
testcase_03 AC 16 ms
8,200 KB
testcase_04 AC 16 ms
8,220 KB
testcase_05 AC 15 ms
8,256 KB
testcase_06 AC 15 ms
8,256 KB
testcase_07 AC 16 ms
8,392 KB
testcase_08 AC 30 ms
8,816 KB
testcase_09 AC 19 ms
8,576 KB
testcase_10 AC 25 ms
8,488 KB
testcase_11 AC 44 ms
8,464 KB
testcase_12 AC 69 ms
9,260 KB
testcase_13 AC 65 ms
9,236 KB
testcase_14 AC 17 ms
8,276 KB
testcase_15 AC 17 ms
8,380 KB
testcase_16 AC 19 ms
8,528 KB
testcase_17 AC 17 ms
8,392 KB
testcase_18 AC 17 ms
8,196 KB
testcase_19 AC 17 ms
8,312 KB
testcase_20 AC 21 ms
8,348 KB
testcase_21 AC 17 ms
8,472 KB
testcase_22 AC 17 ms
8,420 KB
testcase_23 AC 103 ms
8,656 KB
testcase_24 AC 93 ms
8,500 KB
testcase_25 AC 28 ms
8,356 KB
testcase_26 AC 21 ms
8,440 KB
testcase_27 AC 73 ms
8,604 KB
testcase_28 AC 16 ms
8,228 KB
testcase_29 AC 29 ms
8,504 KB
testcase_30 AC 18 ms
8,336 KB
testcase_31 AC 25 ms
8,396 KB
testcase_32 AC 33 ms
8,824 KB
testcase_33 AC 23 ms
8,504 KB
testcase_34 AC 78 ms
8,756 KB
testcase_35 AC 17 ms
8,340 KB
testcase_36 AC 20 ms
8,720 KB
testcase_37 AC 19 ms
8,532 KB
testcase_38 AC 15 ms
8,240 KB
testcase_39 AC 18 ms
8,400 KB
testcase_40 AC 17 ms
8,344 KB
testcase_41 AC 16 ms
8,424 KB
testcase_42 AC 16 ms
8,200 KB
testcase_43 AC 17 ms
8,460 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

# 入力

# N
# C
# V
# S1 S2 S3 … SV
# T1 T2 T3 … TV
# Y1 Y2 Y3 … YV
# M1 M2 M3 … MV
# 1行目に、町の数を表す整数 N (1≤N≤50) が与えられる。
# 2行目に、手持ちのお金を表す整数 C (0≤C≤300) が与えられる。
# 3行目に、道の数を表す整数 V (1≤V≤1500) が与えられる。
# 4行目に、Si (1≤Si<N)がV個スペース区切りで与えられる。
# 5行目に、Ti (Si<Ti≤N)がV個スペース区切りで与えられる。
# 6行目に、Yi (1≤Yi≤C)がV個スペース区切りで与えられる。
# 7行目に、Mi (1≤Mi≤1000)がV個スペース区切りで与えられる。
# ほぼ解説してくれてる方のコードをpythonにしただけ・・・。

import sys
#import os

INF=10e9

class RoadInfo:
	def __init__(self,after_town_index,cost_of_town_to_town,time_town_to_town):
		self.after_town_index=after_town_index
		self.cost_of_town_to_town=cost_of_town_to_town
		self.time_town_to_town=time_town_to_town


# 入力を取得
inStream=sys.stdin
#with open(os.path.abspath('testcase_1_9.txt'),mode='r',encoding='utf-8') as f:
#	inStream=f
# 1<=town_count<=50
town_count=int(inStream.readline())
# 0<=money<=300
start_money=int(inStream.readline())
# 1<=road_count<=1500
road_count=int(inStream.readline())
# (1≤before_town_index<N)
line=inStream.readline()
before_town_index=line.split()
# (before_town_index<after_town_index<N)
line=inStream.readline()
after_town_index=line.split()
# (1<=cost_of_town_to_town<=money)
line=inStream.readline()
cost_of_town_to_town=line.split()
# (1<=time_town_to_town<=1000)
line=inStream.readline()
time_town_to_town=line.split()

roadInfos=[ [] for i in range(town_count)]
for rIndex in range(road_count):
	roadInfos[int(before_town_index[rIndex])-1].append(RoadInfo(int(after_town_index[rIndex])-1, int(cost_of_town_to_town[rIndex]), int(time_town_to_town[rIndex]) ))

# 街1、残金Cから、ある街残金Cへの最小移動時間の配列
time_of_a_to_b=[[ INF for i in range(start_money+1)] for j in range(town_count)]

time_of_a_to_b[0][start_money]=0


for townIndex in range(town_count):
	# 街の数でループ
	# 街ごとに、全部の金のパターンを調査
	for money in range(start_money+1):
		# さらに、金ごとに、全道をループ
		if time_of_a_to_b[townIndex][money] == INF:
			# この街でこの金のパターンが未計算であれば、計算しない
			continue

		#計算済み
		for roadInfo in roadInfos[townIndex]:
			# 移動した場合の残金計算。残金不足ならば、メモしないことによって、そのルートを除外できる
			restMoney = money - roadInfo.cost_of_town_to_town
			if restMoney < 0:
				continue
			# 移動先の街でのその時のコストでの最小時間を更新
			# print("restMoney:{}-{}".format( money, int(cost_of_town_to_town[roadIndex])))
			# print("{}->{}:{}={}".format( before_town_index[roadIndex], after_town_index[roadIndex], restMoney, min(time_of_a_to_b[townIndex][money] + int(time_town_to_town[roadIndex]), \
			# 														time_of_a_to_b[int(after_town_index[roadIndex])-1][restMoney] ) ) )
			# print("{}+{}or{}".format( time_of_a_to_b[townIndex][money], int(time_town_to_town[roadIndex]), \
			# 														time_of_a_to_b[int(after_town_index[roadIndex])-1][restMoney] ) )
			# 今回移動した場合の時間か、すでに計算されているものがあり、その方が小さければ、そちら。
			time_of_a_to_b[roadInfo.after_town_index][restMoney]=min(time_of_a_to_b[townIndex][money] + roadInfo.time_town_to_town, \
																	time_of_a_to_b[roadInfo.after_town_index][restMoney] )


#print(time_of_a_to_b[town_count-1])

# 全コストでループし、その中で一番小さいものを回答とする
ans = INF
for money in range(start_money):
	ans = min( ans, time_of_a_to_b[town_count-1][money] )

if ans == INF:
	print( -1 )
else:
	print( ans )

0