第二回全国統一プログラミング王決定戦予選 D - Shortest Path on a Line

始点ソートして、L ≦ i ≦ R でd[ i ] = min( d[ i ], d[ L ] + c ) で更新していけば終わり。
答えは d[ n-1 ] で、d[ n-1 ] = INF なら -1 を出力する
d[ i ] の一点取得、L ≦ i ≦ R の区間更新なのでセグ木を使えば簡単。

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int,readline().split())
chk = []
for i in range(m):
  l,r,c = map(int,readline().split())
  chk.append((l-1,r-1,c))
  
chk.sort()
class SegmentTree:
    def __init__(self, n, ele, segfun):
        self.ide_ele = ele
        self.segfun = segfun
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [self.ide_ele] * (self.N0 * 2)

    def update(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.segfun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r - 1] = self.segfun(self.data[r - 1], val)
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.segfun(ret, self.data[i])
        return ret

S = SegmentTree(n,10**14,lambda a,b: min(a,b))
S.update(0,1,0)
for l,r,c in chk:
  a = S.query(l)
  S.update(l,r+1,a+c)
  
ans = S.query(n-1)
if ans == 10**14:
  print(-1)
else:
  print(ans)