結果

問題 No.614 壊れたキャンパス
ユーザー 👑 obakyanobakyan
提出日時 2019-05-06 17:22:37
言語 Lua
(LuaJit 2.1.1696795921)
結果
TLE  
実行時間 -
コード長 2,687 bytes
コンパイル時間 465 ms
コンパイル使用メモリ 7,044 KB
実行使用メモリ 454,028 KB
最終ジャッジ日時 2023-09-10 08:21:37
合計ジャッジ時間 5,878 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
11,472 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,384 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

local ior = io.input()
local n, m, k, s, t = ior:read("*n", "*n", "*n", "*n", "*n")
local mmi, mab = math.min, math.abs
local rawbridge, bridge = {}, {}
local buildpos = {}
for i = 1, n - 1 do rawbridge[i], bridge[i] = {}, {} end
for i = 1, n do buildpos[i] = {} end
table.insert(buildpos[1], s)
table.insert(buildpos[n], t)
for i = 1, m do
  local a, b, c = ior:read("*n", "*n", "*n")
  local tmp = {}
  tmp.b, tmp.c = b, c
  table.insert(rawbridge[a], tmp)
  table.insert(buildpos[a], b)
  table.insert(buildpos[a + 1], c)
end

local nodecost = {}
for i = 1, n do
  table.sort(buildpos[i])
  nodecost[i] = {}
  for j = 1, #buildpos[i] do nodecost[i][j] = -1 end
end

local function find_build_pos_idx_from_floor(buildnum, tgtfloor)
  local min, max = 1, #buildpos[buildnum]
  while(true) do
    local mid = math.floor((min + max) / 2)
    local midfl = buildpos[buildnum][mid]
    if(tgtfloor < midfl) then max = mid - 1
    elseif(midfl < tgtfloor) then min = mid + 1
    else return mid
    end
  end
end

for i_b = 1, n - 1 do
  local rbn = #rawbridge[i_b]
  for i_br = 1, rbn do
    local src = find_build_pos_idx_from_floor(i_b, rawbridge[i_b][i_br].b)
    local dst = find_build_pos_idx_from_floor(i_b + 1, rawbridge[i_b][i_br].c)
    if(bridge[i_b][src] == nil) then bridge[i_b][src] = {} end
    table.insert(bridge[i_b][src], dst)
  end
end

local tasks = {}
local function maketask(buildnum, idx)
  local tmp = {}
  tmp.bnum, tmp.idx = buildnum, idx
  table.insert(tasks, tmp)
end
local firstidx = find_build_pos_idx_from_floor(1, s)
nodecost[1][firstidx] = 0
maketask(1, firstidx)
local lastidx = find_build_pos_idx_from_floor(n, t)

local done = 0
while(done < #tasks) do
  done = done + 1
  local bnum, idx = tasks[done].bnum, tasks[done].idx
  if(1 < idx) then
    local candval = nodecost[bnum][idx] + buildpos[bnum][idx] - buildpos[bnum][idx - 1]
    if(nodecost[bnum][idx - 1] == -1 or candval < nodecost[bnum][idx - 1]) then
      nodecost[bnum][idx - 1] = candval
      maketask(bnum, idx - 1)
    end
  end
  if(idx < #buildpos[bnum]) then
    local candval = nodecost[bnum][idx] + buildpos[bnum][idx + 1] - buildpos[bnum][idx]
    if(nodecost[bnum][idx + 1] == -1 or candval < nodecost[bnum][idx + 1]) then
      nodecost[bnum][idx + 1] = candval
      maketask(bnum, idx + 1)
    end
  end
  if(bnum ~= n and bridge[bnum][idx] ~= nil) then
    for i_br = 1, #bridge[bnum][idx] do
      local i_nx = bridge[bnum][idx][i_br]
      if(nodecost[bnum + 1][i_nx] == -1 or nodecost[bnum][idx] < nodecost[bnum + 1][i_nx]) then
        nodecost[bnum + 1][i_nx] = nodecost[bnum][idx]
        maketask(bnum + 1, i_nx)
      end
    end
  end
end
print(nodecost[n][lastidx])
0