#56900 (Python3) No.1 道のショートカット

提出ソース

結果

問題	No.1 道のショートカット
ユーザー	yuma25689
提出日時	2015-11-04 15:30:46
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	RE
実行時間	-
コード長	3,934 bytes
コンパイル時間	82 ms
コンパイル使用メモリ	12,672 KB
実行使用メモリ	11,776 KB
最終ジャッジ日時	2024-07-08 04:15:21
合計ジャッジ時間	3,210 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	29 ms 10,880 KB
testcase_01	AC	29 ms 10,752 KB
testcase_02	AC	28 ms 10,752 KB
testcase_03	AC	31 ms 10,752 KB
testcase_04	AC	32 ms 10,752 KB
testcase_05	AC	31 ms 10,752 KB
testcase_06	AC	30 ms 10,752 KB
testcase_07	AC	32 ms 10,752 KB
testcase_08	AC	45 ms 11,008 KB
testcase_09	AC	36 ms 11,136 KB
testcase_10	AC	42 ms 11,008 KB
testcase_11	AC	65 ms 11,136 KB
testcase_12	AC	96 ms 11,520 KB
testcase_13	AC	89 ms 11,776 KB
testcase_14	AC	31 ms 10,752 KB
testcase_15	RE	-
testcase_16	AC	34 ms 10,752 KB
testcase_17	RE	-
testcase_18	AC	31 ms 10,752 KB
testcase_19	AC	32 ms 10,752 KB
testcase_20	AC	37 ms 10,624 KB
testcase_21	AC	35 ms 10,752 KB
testcase_22	AC	32 ms 10,752 KB
testcase_23	AC	130 ms 11,136 KB
testcase_24	AC	125 ms 11,008 KB
testcase_25	AC	46 ms 10,752 KB
testcase_26	AC	39 ms 10,624 KB
testcase_27	AC	101 ms 11,136 KB
testcase_28	RE	-
testcase_29	AC	47 ms 11,136 KB
testcase_30	AC	33 ms 10,880 KB
testcase_31	AC	45 ms 10,880 KB
testcase_32	AC	53 ms 11,008 KB
testcase_33	AC	39 ms 10,880 KB
testcase_34	AC	106 ms 11,264 KB
testcase_35	AC	33 ms 10,752 KB
testcase_36	AC	37 ms 11,136 KB
testcase_37	AC	34 ms 10,880 KB
testcase_38	AC	31 ms 10,752 KB
testcase_39	AC	35 ms 10,752 KB
testcase_40	AC	32 ms 10,880 KB
testcase_41	AC	30 ms 10,880 KB
testcase_42	RE	-
testcase_43	RE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

# 入力

# 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(road_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 )

yukicoder

結果

テストケース

ソースコード