結果

問題 No.160 最短経路のうち辞書順最小
ユーザー 👑 obakyan
提出日時 2020-04-20 22:47:42
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 12 ms / 5,000 ms
コード長 1,510 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 6,948 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-06 09:33:05
合計ジャッジ時間 1,534 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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