Submission #69145173

Source Code Expand

INF = 1 << 60
N, M = gets.split.map(&:to_i)
W = gets.split.map(&:to_i)
edges = Array.new(M) do
  gets.split.map(&:to_i).map(&:pred)
end

# dp[v] := 頂点vを訪れたときの最小コスト
dp = Array.new(N, INF)

# i := 残りの移動する回数
(N - 1).downto(0) do |i|
  ep = Array.new(N, INF)
  ep[0] = W[0] * i
  edges.each do |u, v|
    ep[v] = [ep[v], dp[u] + W[v] * i].min
    ep[u] = [ep[u], dp[v] + W[u] * i].min
  end
  dp = ep
end

puts dp

Submission Info

Submission Time
Task F - Eat and Ride
User fumta
Language Ruby (ruby 3.2.2)
Score 0
Code Size 478 Byte
Status TLE
Exec Time 2213 ms
Memory 99068 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 28
TLE × 23
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt, 01_random_49.txt, 01_random_50.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 137 ms 17348 KiB
00_sample_01.txt AC 43 ms 17260 KiB
00_sample_02.txt AC 44 ms 17348 KiB
01_random_03.txt AC 759 ms 46544 KiB
01_random_04.txt AC 672 ms 45980 KiB
01_random_05.txt AC 363 ms 23764 KiB
01_random_06.txt AC 534 ms 47532 KiB
01_random_07.txt AC 412 ms 43556 KiB
01_random_08.txt AC 832 ms 43384 KiB
01_random_09.txt AC 182 ms 18516 KiB
01_random_10.txt AC 159 ms 25292 KiB
01_random_11.txt TLE 2202 ms 96796 KiB
01_random_12.txt TLE 2213 ms 96360 KiB
01_random_13.txt TLE 2208 ms 95984 KiB
01_random_14.txt TLE 2203 ms 96256 KiB
01_random_15.txt TLE 2204 ms 96092 KiB
01_random_16.txt TLE 2213 ms 97156 KiB
01_random_17.txt TLE 2213 ms 96304 KiB
01_random_18.txt TLE 2205 ms 96252 KiB
01_random_19.txt TLE 2201 ms 96976 KiB
01_random_20.txt TLE 2184 ms 96692 KiB
01_random_21.txt TLE 2187 ms 96348 KiB
01_random_22.txt TLE 2197 ms 96924 KiB
01_random_23.txt TLE 2199 ms 97192 KiB
01_random_24.txt TLE 2189 ms 96744 KiB
01_random_25.txt TLE 2196 ms 97248 KiB
01_random_26.txt TLE 2137 ms 96092 KiB
01_random_27.txt TLE 2187 ms 96960 KiB
01_random_28.txt TLE 2213 ms 97004 KiB
01_random_29.txt TLE 2213 ms 97192 KiB
01_random_30.txt TLE 2188 ms 96948 KiB
01_random_31.txt AC 568 ms 31688 KiB
01_random_32.txt AC 1159 ms 69612 KiB
01_random_33.txt AC 358 ms 21984 KiB
01_random_34.txt AC 1323 ms 81420 KiB
01_random_35.txt AC 385 ms 22688 KiB
01_random_36.txt AC 980 ms 60284 KiB
01_random_37.txt AC 1949 ms 86076 KiB
01_random_38.txt AC 1056 ms 60700 KiB
01_random_39.txt AC 526 ms 27748 KiB
01_random_40.txt AC 258 ms 19568 KiB
01_random_41.txt AC 1799 ms 94700 KiB
01_random_42.txt AC 1748 ms 99068 KiB
01_random_43.txt AC 1715 ms 97276 KiB
01_random_44.txt AC 1719 ms 97840 KiB
01_random_45.txt AC 1805 ms 94492 KiB
01_random_46.txt AC 1157 ms 68744 KiB
01_random_47.txt AC 1173 ms 68988 KiB
01_random_48.txt TLE 2213 ms 96292 KiB
01_random_49.txt TLE 2211 ms 97132 KiB
01_random_50.txt TLE 2208 ms 96984 KiB