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

提出ソース

結果

問題	No.1 道のショートカット
ユーザー	yuma25689
提出日時	2015-11-04 15:33:34
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	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

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	27 ms 10,880 KB
testcase_01	AC	28 ms 10,752 KB
testcase_02	AC	28 ms 10,752 KB
testcase_03	AC	27 ms 10,752 KB
testcase_04	AC	28 ms 10,752 KB
testcase_05	AC	25 ms 10,752 KB
testcase_06	AC	31 ms 10,752 KB
testcase_07	AC	26 ms 10,880 KB
testcase_08	AC	39 ms 11,136 KB
testcase_09	AC	31 ms 11,136 KB
testcase_10	AC	37 ms 11,136 KB
testcase_11	AC	56 ms 11,136 KB
testcase_12	AC	84 ms 11,520 KB
testcase_13	AC	81 ms 11,520 KB
testcase_14	AC	27 ms 10,752 KB
testcase_15	AC	28 ms 10,880 KB
testcase_16	AC	28 ms 10,880 KB
testcase_17	AC	27 ms 10,880 KB
testcase_18	AC	27 ms 10,752 KB
testcase_19	AC	27 ms 10,752 KB
testcase_20	AC	32 ms 10,752 KB
testcase_21	AC	28 ms 10,880 KB
testcase_22	AC	27 ms 10,752 KB
testcase_23	AC	113 ms 11,136 KB
testcase_24	AC	112 ms 11,008 KB
testcase_25	AC	43 ms 10,880 KB
testcase_26	AC	32 ms 10,752 KB
testcase_27	AC	92 ms 11,136 KB
testcase_28	AC	26 ms 10,752 KB
testcase_29	AC	40 ms 11,136 KB
testcase_30	AC	27 ms 10,880 KB
testcase_31	AC	37 ms 11,008 KB
testcase_32	AC	45 ms 11,136 KB
testcase_33	AC	35 ms 11,136 KB
testcase_34	AC	93 ms 11,392 KB
testcase_35	AC	28 ms 10,880 KB
testcase_36	AC	33 ms 11,008 KB
testcase_37	AC	29 ms 11,008 KB
testcase_38	AC	25 ms 10,880 KB
testcase_39	AC	27 ms 11,008 KB
testcase_40	AC	26 ms 10,880 KB
testcase_41	AC	29 ms 10,880 KB
testcase_42	AC	28 ms 10,880 KB
testcase_43	AC	28 ms 10,880 KB

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

ソースコード

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

yukicoder

結果

テストケース

ソースコード