結果

問題 No.614 壊れたキャンパス
ユーザー 👑 obakyanobakyan
提出日時 2019-05-06 19:41:30
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 1,056 ms / 2,000 ms
コード長 2,848 bytes
コンパイル時間 88 ms
コンパイル使用メモリ 5,336 KB
実行使用メモリ 120,324 KB
最終ジャッジ日時 2023-09-10 12:43:05
合計ジャッジ時間 13,255 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 955 ms
67,488 KB
testcase_09 AC 1,008 ms
63,876 KB
testcase_10 AC 1,056 ms
114,740 KB
testcase_11 AC 856 ms
62,276 KB
testcase_12 AC 933 ms
62,344 KB
testcase_13 AC 920 ms
62,324 KB
testcase_14 AC 970 ms
68,004 KB
testcase_15 AC 949 ms
89,468 KB
testcase_16 AC 954 ms
72,124 KB
testcase_17 AC 634 ms
120,324 KB
testcase_18 AC 709 ms
43,524 KB
testcase_19 AC 774 ms
52,872 KB
権限があれば一括ダウンロードができます

ソースコード

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 = {}
local tblins = table.insert
for i = 1, n - 1 do rawbridge[i], bridge[i] = {}, {} end
for i = 1, n do buildpos[i] = {} end
tblins(buildpos[1], s)
tblins(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
  tblins(rawbridge[a], tmp)
  if(not bposadded[a][b]) then
    tblins(buildpos[a], b)
    bposadded[a][b] = true
  end
  if(not bposadded[a + 1][c]) then
    tblins(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
    tblins(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