結果

問題 No.160 最短経路のうち辞書順最小
ユーザー 👑 obakyanobakyan
提出日時 2020-04-20 22:47:42
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 14 ms / 5,000 ms
コード長 1,510 bytes
コンパイル時間 214 ms
コンパイル使用メモリ 6,944 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-16 01:04:06
合計ジャッジ時間 1,645 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 7 ms
5,376 KB
testcase_05 AC 11 ms
5,376 KB
testcase_06 AC 14 ms
5,376 KB
testcase_07 AC 5 ms
5,376 KB
testcase_08 AC 5 ms
5,376 KB
testcase_09 AC 4 ms
5,376 KB
testcase_10 AC 5 ms
5,376 KB
testcase_11 AC 6 ms
5,376 KB
testcase_12 AC 4 ms
5,376 KB
testcase_13 AC 5 ms
5,376 KB
testcase_14 AC 4 ms
5,376 KB
testcase_15 AC 4 ms
5,376 KB
testcase_16 AC 4 ms
5,376 KB
testcase_17 AC 4 ms
5,376 KB
testcase_18 AC 4 ms
5,376 KB
testcase_19 AC 5 ms
5,376 KB
testcase_20 AC 4 ms
5,376 KB
testcase_21 AC 4 ms
5,376 KB
testcase_22 AC 4 ms
5,376 KB
testcase_23 AC 5 ms
5,376 KB
testcase_24 AC 5 ms
5,376 KB
testcase_25 AC 4 ms
5,376 KB
testcase_26 AC 5 ms
5,376 KB
testcase_27 AC 3 ms
5,376 KB
testcase_28 AC 14 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

local mmi, mma = math.min, math.max
local n, m, s, g = io.read("*n", "*n", "*n", "*n")
s, g = s + 1, g + 1
local edge = {}
local inf = 1000000007
for i = 1, n do
  edge[i] = {}
end
for i = 1, m do
  local a, b, c = io.read("*n", "*n", "*n")
  a, b = a + 1, b + 1
  edge[a][b] = c
  edge[b][a] = c
end

local function getlength(start_idx, dst_idx)
  local taskstate = {}
  for i = 1, n do taskstate[i] = false end
  local tasks = {}
  local tasknum = 0
  local done = 0

  local len = {}
  for i = 1, n do len[i] = inf end
  len[start_idx] = 0

  local function addtask(idx)
    if not taskstate[idx] then
      taskstate[idx] = true
      tasknum = tasknum + 1
      tasks[tasknum] = idx
    end
  end
  addtask(start_idx)

  while done < tasknum do
    done = done + 1
    local src = tasks[done]
    taskstate[src] = false
    local tmp = {}
    for dst, cost in pairs(edge[src]) do
      if len[src] + cost < len[dst] then
        len[dst] = len[src] + cost
        -- addtask(dst)
        table.insert(tmp, dst)
      end
    end
    table.sort(tmp, function(a, b) return len[a] < len[b] end)
    for i = 1, #tmp do addtask(tmp[i]) end
  end
  return len
end
local len = getlength(g, s)
local ret = {s}
local pos = s
while pos ~= g do
  local dstcand = inf
  for dst, cost in pairs(edge[pos]) do
    if len[pos] == len[dst] + cost then
      dstcand = mmi(dstcand, dst)
    end
  end
  table.insert(ret, dstcand)
  pos = dstcand
end
for i = 1, #ret do ret[i] = ret[i] - 1 end
print(table.concat(ret, " "))
0