結果

問題 No.1 道のショートカット
ユーザー kou_kkk
提出日時 2025-08-04 01:39:50
言語 Nim
(2.2.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 888 bytes
コンパイル時間 5,120 ms
コンパイル使用メモリ 70,324 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-04 01:39:58
合計ジャッジ時間 7,112 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sequtils, strutils, sugar

let
  # 街の数、持ち金、道の数
  n, c, v = parseInt stdin.readLine
  # 発、着、費用、時間
  s, t, y, m = stdin.readLine.split.map parseInt

var
  # (行き先、費用、時間)
  g = newSeq[seq[(int, int, int)]](n)
  # [合計費用](合計時間)
  dp = newSeqWith(n, (-1).repeat c+1)

for i in 0 .. v-1:
  g[s[i]-1].add (t[i]-1, y[i], m[i])

dp[0][0] = 0

for i in 0 ..< n-1:
  for j in 0 .. c:
    let
      timeX = dp[i][j]
    if timeX == -1: continue
    for (node, yenY, timeY) in g[i]:
      let
        yen = j + yenY
        time = timeX + timeY
      if yen > c: continue
      let
        next = dp[node][yen]
      if next != -1 and next <= time: continue
      dp[node][yen] = time

let
  times = newSeq.collect:
            for a in dp[n-1]:
              if a != -1: a

echo:
  if times.len == 0: -1
  else: min times
0