結果

問題 No.1 道のショートカット
コンテスト
ユーザー yuma25689
提出日時 2015-11-04 15:33:34
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 113 ms / 5,000 ms
コード長 3,933 bytes
コンパイル時間 230 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,520 KB
最終ジャッジ日時 2024-07-20 16:17:56
合計ジャッジ時間 2,794 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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