結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
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, " "))