結果

問題 No.2366 登校
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:57:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,440 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 86,228 KB
最終ジャッジ日時 2025-03-26 15:59:21
合計ジャッジ時間 4,011 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    n, m, k, T = map(int, input().split())
    myst = {}
    for _ in range(k):
        a, b, c, d = map(int, input().split())
        a -= 1
        b -= 1
        myst[(a, b)] = (c, d)
    
    start_i, start_j = 0, 0
    end_i, end_j = n - 1, m - 1

    best = {}
    heap = []
    initial_state = (start_i, start_j, True)
    best[initial_state] = {0: 0}
    heapq.heappush(heap, (0, start_i, start_j, True, 0))

    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    found = False
    answer = -1

    while heap:
        sum_d, i, j, can_move, adj_time = heapq.heappop(heap)
        
        if i == end_i and j == end_j and adj_time <= T:
            answer = sum_d
            found = True
            break
        
        current_key = (i, j, can_move)
        if current_key not in best:
            continue
        current_best = best[current_key]
        if sum_d not in current_best or current_best[sum_d] < adj_time:
            continue
        
        if can_move:
            for di, dj in dirs:
                ni, nj = i + di, j + dj
                if 0 <= ni < n and 0 <= nj < m:
                    new_sum_d = sum_d
                    new_adj_time = adj_time + 1
                    if new_adj_time > T:
                        continue
                    new_key = (ni, nj, True)
                    if new_key not in best:
                        best[new_key] = {}
                    entry = best[new_key]
                    add = True
                    remove = []
                    for d_entry in list(entry.keys()):
                        if d_entry <= new_sum_d and entry[d_entry] <= new_adj_time:
                            add = False
                            break
                    if add:
                        for d_entry in list(entry.keys()):
                            if d_entry >= new_sum_d and entry[d_entry] >= new_adj_time:
                                remove.append(d_entry)
                        for d in remove:
                            del entry[d]
                        entry[new_sum_d] = new_adj_time
                        heapq.heappush(heap, (new_sum_d, ni, nj, True, new_adj_time))
            
            if (i, j) in myst:
                c, d = myst[(i, j)]
                new_sum_d = sum_d + d
                new_adj_time = adj_time + 1 - c
                new_can_move = False
                if new_adj_time > T:
                    continue
                new_key = (i, j, new_can_move)
                if new_key not in best:
                    best[new_key] = {}
                entry = best[new_key]
                add = True
                remove = []
                for d_entry in list(entry.keys()):
                    if d_entry <= new_sum_d and entry[d_entry] <= new_adj_time:
                        add = False
                        break
                if add:
                    for d_entry in list(entry.keys()):
                        if d_entry >= new_sum_d and entry[d_entry] >= new_adj_time:
                            remove.append(d_entry)
                    for d in remove:
                        del entry[d]
                    entry[new_sum_d] = new_adj_time
                    heapq.heappush(heap, (new_sum_d, i, j, new_can_move, new_adj_time))
        else:
            new_sum_d = sum_d
            new_adj_time = adj_time + 1
            new_can_move = True
            if new_adj_time > T:
                continue
            new_key = (i, j, new_can_move)
            if new_key not in best:
                best[new_key] = {}
            entry = best[new_key]
            add = True
            remove = []
            for d_entry in list(entry.keys()):
                if d_entry <= new_sum_d and entry[d_entry] <= new_adj_time:
                    add = False
                    break
            if add:
                for d_entry in list(entry.keys()):
                    if d_entry >= new_sum_d and entry[d_entry] >= new_adj_time:
                        remove.append(d_entry)
                for d in remove:
                    del entry[d]
                entry[new_sum_d] = new_adj_time
                heapq.heappush(heap, (new_sum_d, i, j, new_can_move, new_adj_time))
            
            if (i, j) in myst:
                c, d = myst[(i, j)]
                new_sum_d = sum_d + d
                new_adj_time = adj_time + 1 - c
                new_can_move = False
                if new_adj_time > T:
                    continue
                new_key = (i, j, new_can_move)
                if new_key not in best:
                    best[new_key] = {}
                entry = best[new_key]
                add = True
                remove = []
                for d_entry in list(entry.keys()):
                    if d_entry <= new_sum_d and entry[d_entry] <= new_adj_time:
                        add = False
                        break
                if add:
                    for d_entry in list(entry.keys()):
                        if d_entry >= new_sum_d and entry[d_entry] >= new_adj_time:
                            remove.append(d_entry)
                    for d in remove:
                        del entry[d]
                    entry[new_sum_d] = new_adj_time
                    heapq.heappush(heap, (new_sum_d, i, j, new_can_move, new_adj_time))
    
    print(answer if found else -1)

if __name__ == "__main__":
    main()
0