結果

問題 No.614 壊れたキャンパス
コンテスト
ユーザー 👑 obakyan
提出日時 2019-05-06 19:30:28
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 1,011 ms / 2,000 ms
コード長 2,856 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 5,376 KB
実行使用メモリ 164,480 KB
最終ジャッジ日時 2024-06-28 03:00:36
合計ジャッジ時間 11,630 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

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)
local bposadded = {}
for i = 1, n do bposadded[i] = {} end
bposadded[1][s] = true
bposadded[n][t] = true
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)
  if(not bposadded[a][b]) then
    table.insert(buildpos[a], b)
    bposadded[a][b] = true
  end
  if(not bposadded[a + 1][c]) then
    table.insert(buildpos[a + 1], c)
    bposadded[a + 1][c] = true
  end
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 firstidx = find_build_pos_idx_from_floor(1, s)
local lastidx = find_build_pos_idx_from_floor(n, t)
nodecost[1][firstidx] = 0

for bnum = 1, n do
  local posnum = #buildpos[bnum]
  for i_pos = 1, posnum - 1 do
    if(0 <= nodecost[bnum][i_pos]) then
      local candval = nodecost[bnum][i_pos] + buildpos[bnum][i_pos + 1] - buildpos[bnum][i_pos]
      if(nodecost[bnum][i_pos + 1] == -1 or candval < nodecost[bnum][i_pos + 1]) then
        nodecost[bnum][i_pos + 1] = candval
      end
    end
  end
  for i_pos = posnum, 2, -1 do
    if(0 <= nodecost[bnum][i_pos]) then
      local candval = nodecost[bnum][i_pos] + buildpos[bnum][i_pos] - buildpos[bnum][i_pos - 1]
      if(nodecost[bnum][i_pos - 1] == -1 or candval < nodecost[bnum][i_pos - 1]) then
        nodecost[bnum][i_pos - 1] = candval
      end
    end
  end
  if(bnum ~= n) then
    for i_pos = 1, posnum do
      if(bridge[bnum][i_pos] ~= nil) then
        for i_br = 1, #bridge[bnum][i_pos] do
          local i_nx = bridge[bnum][i_pos][i_br]
          if(nodecost[bnum + 1][i_nx] == -1 or nodecost[bnum][i_pos] < nodecost[bnum + 1][i_nx]) then
            nodecost[bnum + 1][i_nx] = nodecost[bnum][i_pos]
          end
        end
      end
    end
  end
end
print(nodecost[n][lastidx])
0