結果

問題 No.2477 Drifting
コンテスト
ユーザー LyricalMaestro
提出日時 2025-01-01 16:56:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,532 ms / 2,000 ms
コード長 3,639 bytes
コンパイル時間 384 ms
コンパイル使用メモリ 82,568 KB
実行使用メモリ 196,728 KB
最終ジャッジ日時 2025-01-01 16:56:19
合計ジャッジ時間 15,573 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2477

MAX_INT = 10 ** 18

class SegmentTree:
    """
    非再帰版セグメント木。
    更新は「加法」、取得は「最大値」のもの限定。
    """

    def __init__(self, init_array):
        n = 1
        while n < len(init_array):
            n *= 2
        
        self.size = n
        self.array = [[MAX_INT, MAX_INT] for _ in range(2 * self.size)]
        for i, a in enumerate(init_array):
            self.array[self.size + i][0] = a
            self.array[self.size + i][1] = i
        
        end_index = self.size
        start_index = end_index // 2
        while start_index >= 1:
            for i in range(start_index, end_index):
                self._op(self.array[i], self.array[2 * i], self.array[2 * i + 1])
            end_index = start_index
            start_index = end_index // 2
    
    def _op(self, array, left, right):
        if left[0] < right[0]:
            array[0] = left[0]
            array[1] = left[1]
        elif left[0] > right[0]:
            array[0] = right[0]
            array[1] = right[1]
        else:
            array[0] = left[0]
            array[1] = min(left[1], right[1])

    def set(self, x, a):
        index = self.size + x
        self.array[index][0] = a
        while index > 1:
            index //= 2
            self._op(self.array[index], self.array[2 * index], self.array[2 * index + 1])

    def get_min(self, l, r):
        L = self.size + l; R = self.size + r

        # 2. 区間[l, r)の最大値を求める
        s = [MAX_INT, MAX_INT]
        while L < R:
            if R & 1:
                R -= 1
                self._op(s, s, self.array[R])
            if L & 1:
                self._op(s, s, self.array[L])
                L += 1
            L >>= 1; R >>= 1
        return s


def main():
    N, M = map(int, input().split())
    next_nodes = [[] for _ in range(N)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        next_nodes[u - 1].append((v - 1, w))
    
    K = int(input())
    state_base_map = {}
    for _ in range(K):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        c -= 1
        if (b, c) not in state_base_map:
            state_base_map[(b, c)] = set()
        state_base_map[(b, c)].add(a)

    dp = [{} for _ in range(N)]
    dp[0][-1] = 0
    for s_n in range(N):
        if len(dp[s_n]) == 0:
            continue

        array1 = [(prev, cost) for prev, cost in dp[s_n].items()]
        array2 = [cost for _, cost in array1]
        prev_index_map = {array1[index][0]:index for index in range(len(array1))}

        seg_tree = SegmentTree(array2)
        for next_n, w in next_nodes[s_n]:
            forbidden = []
            if (s_n, next_n) in state_base_map:
                forbidden = state_base_map[(s_n, next_n)]
            
            for prev in forbidden:
                if prev in prev_index_map:
                    seg_tree.set(prev_index_map[prev], MAX_INT)
            
            s = seg_tree.get_min(0, len(array2))
            new_cost = s[0] + w
            if s_n not in dp[next_n]:
                dp[next_n][s_n] = MAX_INT
            dp[next_n][s_n] = min(dp[next_n][s_n], new_cost)

            for prev in forbidden:
                if prev in prev_index_map:
                    ii = prev_index_map[prev]
                    seg_tree.set(ii, array2[ii])
    
    
    answer = MAX_INT
    for cost in dp[-1].values():
        answer = min(answer, cost)
    if answer == MAX_INT:
        print(-1)
    else:
        print(answer)




    





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