Problem:


Score : 600 points

Problem Statement

We have N points numbered 1 to N arranged in a line in this order.

Takahashi decides to make an undirected graph, using these points as the vertices.
In the beginning, the graph has no edge. Takahashi will do M operations to add edges in this graph.
The i-th operation is as follows:

The operation uses integers L_i and R_i between 1 and N (inclusive), and a positive integer C_i. For every pair of integers (s, t) such that L_i \leq s < t \leq R_i, add an edge of length C_i between Vertex s and Vertex t.

The integers L_1, ..., L_M, R_1, ..., R_M, C_1, ..., C_M are all given as input.

Takahashi wants to solve the shortest path problem in the final graph obtained. Find the length of the shortest path from Vertex 1 to Vertex N in the final graph.

Constraints

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq L_i < R_i \leq N

1 \leq C_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 C_1
:
L_M R_M C_M

Output

Print the length of the shortest path from Vertex 1 to Vertex N in the final graph.
If there is no shortest path, print -1 instead.

Sample Input 1

4 3
1 3 2
2 4 3
1 4 6

Sample Output 1

5

We have an edge of length 2 between Vertex 1 and Vertex 2, and an edge of length 3 between Vertex 2 and Vertex 4, so there is a path of length 5 between Vertex 1 and Vertex 4.

Sample Input 2

4 2
1 2 1
3 4 2

Sample Output 2

-1

Sample Input 3

10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3

Sample Output 3

28



Sample input:
4 3
1 3 2
2 4 3
1 4 6


Sample output:
5

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import heapq

def dijkstra(Route,v,start):
    Dist=[float('inf')]*v
    Dist[start]=0
    Visited=[False]*v
    hq=[(0,start)]
    while hq:
        dist,fr=heapq.heappop(hq)
        Visited[fr]=True
        for to,cost in Route[fr]:
            if (not Visited[to]) and Dist[to]>dist+cost:
                Dist[to]=dist+cost
                heapq.heappush(hq,(Dist[to],to))
    return Dist

def main():
    n,m=map(int,input().split())
    Edges=[[] for _ in range(n)]
    for i in range(n-1):
        Edges[i+1].append((i,0))
    for _ in range(m):
        l,r,c=map(int,input().split())
        l-=1; r-=1
        Edges[l].append((r,c))
    Dist=dijkstra(Edges,n,0)
    print(-1 if Dist[-1]==float('inf') else Dist[-1])
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for i in range(N)]
    for i in range(1, N):
        Edge[i].append((0, i - 1))
    for _ in range(M):
        L, R, C = map(int, input().split())
        Edge[L-1].append((C, R-1))
    
    Dist = [-1] * N
    Q = []
    heapify(Q)
    heappush(Q, (0, 0))
    while Q:
        nowcost, nownode = heappop(Q)
        if Dist[nownode] == -1:
            Dist[nownode] = nowcost
            for addcost, nextnode in Edge[nownode]:
                if Dist[nextnode] == -1:
                    heappush(Q, (nowcost + addcost, nextnode))
    print(Dist[N-1])

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import heapq
n,m=map(int,input().split())

def dijkstra_heap(s):
  d=[float("inf")]*n
  used=[True]*n
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    d[v] = minedge[0]
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1]])
  return d
edge = [[] for i in range(n)]
for i in range(m):
  l,r,c=map(int,input().split())
  edge[l-1].append([c,r-1])
for i in range(1,n):
  edge[i].append([0,i-1])


d=dijkstra_heap(0)
print(-1 if d[-1]==float("inf") else d[-1])

Submission status: Accepted

Solution code:
import heapq


def main():
    n, m = map(int, input().split())
    lrc = [list(map(int, input().split())) for _ in range(m)]

    adj = [[(0, i-1)] for i in range(n)]
    adj[0] = []

    for l, r, c in lrc:
        l -= 1
        r -= 1
        adj[l].append((c, r))

    WHITE = 0
    GRAY = 1
    BLACK = 2

    def dijkstra(s):
        colors = [WHITE] * n
        ds = [float("inf")] * n
        ps = [-1] * n
        pq = []

        ds[s] = 0
        ps[s] = -1
        heapq.heappush(pq, (0, s))

        while pq:
            d, u = heapq.heappop(pq)
            colors[u] = BLACK

            if ds[u] < d:
                continue

            for c, v in adj[u]:
                if colors[v] != BLACK:
                    if ds[u] + c < ds[v]:
                        ds[v] = ds[u] + c
                        ps[v] = u
                        colors[v] = GRAY
                        heapq.heappush(pq, (ds[v], v))

        return ds, ps

    ds, ps = dijkstra(0)

    ans = ds[-1]
    if ans == float("inf"):
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d



n,m=map(int,input().split())#n:頂点数　w:辺の数

edge = [[] for i in range(n)] #edge[i] : iから出る道の[重み,行先]の配列

l=[list(map(int,input().split())) for i in range(m)]
for i in range(m):
    x,y,z =l[i][0],l[i][1],l[i][2]
    x-=1
    y-=1
    edge[x].append([z,y])
    edge[y].append([z,x])
for i in range(1,n):
    edge[i].append([0,i-1])
#print(edge)
#print(dijkstra_heap(0))
a=dijkstra_heap(0)

if a[-1]==float('inf'):
    print(-1)
else:
    print(a[-1])

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(m)]
    a.sort()
    INF = 10 ** 18
    dp = [INF for i in range(n)]
    dp[0] = 0
    for l, r, c in a:
        if dp[l - 1] == INF:
            print(-1)
            return None
        tp = dp[l - 1] + c
        for i in range(r - 1, l - 1, -1):
            if dp[i] == INF:
                dp[i] = tp
            elif tp < dp[i]:
                dp[i] = tp
            else:
                break
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq
input = lambda: sys.stdin.buffer.readline()[:-1].decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

n,m=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(m)]
LRC.sort(key=lambda tup:tup[1])

#####segfunc######
def segfunc(x,y):
   return min(x,y)


def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1] = init_val[i]
    #built
    for i in range(num-2, -1, -1):
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])


def update(k, x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1], seg[k*2+2])


def query(p, q):
    if q <= p:
        return ide_ele
    p += num-1
    q += num-2
    res = ide_ele
    while q-p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res


#####単位元######
ide_ele =inf

#num:n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [ide_ele]*2*num

dp=[inf]*(n)
dp[0]=0

init(dp)



for L,R,C in LRC:
    L-=1;R-=1
    # print(query(L, R))
    dp[R] = min(dp[R], query(L, R)+C)
    update(R, dp[R])

print(dp[n-1] if dp[n-1]!=inf else -1)
# print(dp[:10])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, values, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [self.default] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size-1, 0, -1):
            self.tree[i] = min(self.tree[i*2], self.tree[i*2+1])

    def update(self, index, value):
        index += self.size
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = min(
                self.tree[index*2], self.tree[index*2+1])

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.default
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return min(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


def main():
    N, M = map(int, input().split())
    op = [None] * M
    for i in range(M):
        L, R, C = map(int, input().split())
        op[i] = (L-1, R-1, C)
    op.sort()
    tree = SegmentTree([float("inf")] * N)
    tree.update(0, 0)
    for l, r, c in op:
        mn = tree.query(l, r)
        current = tree.tree[tree.size + r]
        if mn+c < current:
            tree.update(r, mn+c)
    ans = tree.query(N-1, N)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
words = lambda t : list(map(t, input().split()))
n,m = words(int)
xs = []
for i in range(m):
    a,b,c = words(int)
    xs.append((b,a,c))

sxs = reversed(sorted(xs))

ans = [-1] * n
ans[-1] = 0
#print(sxs)
for b,a,c in sxs:
    #print(ans, a,b,c)
    if ans[b-1] == -1:
        #print("con")
        continue
    for i in range(a-1,b-1):
        if ans[i] != -1 and ans[i] <= ans[b-1] + c:
            break
        ans[i] = ans[b-1] + c

print(ans[0])

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())

items = []
for _ in range(M):
	l, r, c = map(int, input().split())
	items.append([l, r, c])

items.sort()
def check():
	queue = []
	index = 0
	data = [None]
	dists = [None, 0]
	for i in range(1, N):
		while index < M:
			l, r, c = items[index]
			if l <= i:
				heapq.heappush(queue, (c + dists[i], -r))
				index += 1
			else:
				break
		while True:
			if len(queue) == 0:
				return None
			c, r = queue[0]
			if -r > i:
				break
			heapq.heappop(queue)
		data.append((c, -r))
		dists.append(c)
	return dists

data = check()
if data != None:
	print(data[N])
else:
	print(-1)

Submission status: Accepted

Solution code:
def main():    
    n,m = map(int,input().split())
    lrc = [tuple(map(int,input().split())) for _ in range(m)]
    lcr = sorted([(i[0]-1,i[2],i[1]-1) for i in lrc],reverse=True)
    INF = float('inf')
    dist = [INF]*n
    check = [False]*n
    check[0] = True
    dist[0] = 0
    enable = True
    while lcr:
        route = lcr.pop(-1)
        mn = route[0]
        mx = route[-1]
        if not check[mn]:
            enable = False
            break
        else:
            d = route[1]+dist[mn]
            for i in range(mx,mn,-1):
                if dist[i] >= d:
                    dist[i] = d
                    check[i] = True
                else:
                    break
    if dist[-1] == INF:
        print(-1)
    elif enable:
        print(dist[-1])
    else:
        print(-1)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
n, m = [int(i) for i in input().split()]
lrc = []
for _ in range(m):
    l, r, c = [int(i) for i in input().split()]
    lrc.append([l-1, r-1, c])
lrc.sort()
a = []
j = 0
for i in range(n-1):
    new = []
    while j < m and lrc[j][0] == i:
        new.append(lrc[j])
        j += 1
    if i == 0:
        now = 0
    else:
        while True:
            if len(a) == 0:
                print(-1)
                exit()
            now = heapq.heappop(a)
            if now[1] >= i:
                heapq.heappush(a, now)
                break
        now = now[0]
    for k in new:
        heapq.heappush(a,[now + k[2], k[1]])


while True:
    if len(a) == 0:
        print(-1)
        exit()
    now = heapq.heappop(a)
    if now[1] >= n-1:
        heapq.heappush(a, now)
        break
now = now[0]
print(now)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import heapq
n,m=map(int,input().split())

D=[0]
P=[]
ans=float("inf")

for i in range(m):
  l,r,c=map(int,input().split())
  P.append((l,r,c))
P.sort(key=lambda x:x[0])
heapq.heappush(D,0*10**15+1)
for l,r,c in P:
  while D:
    ld=heapq.heappop(D)
    dd=ld//(10**15)
    ll=ld%(10**15)
    if ll<l:
      continue
    else:
      break
  if ll>=l:
    heapq.heappush(D,r+(dd+c)*10**15)
  heapq.heappush(D,ll+dd*10**15)
while D:
  ld=heapq.heappop(D)
  dd=ld//(10**15)
  ll=ld%(10**15)
  if ll==n:
    ans=min(ans,dd)
print(-1 if ans==float("inf") else ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from operator import itemgetter
from heapq import heappop, heappush
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M = inpl()
D = [0] + [10**18]*(N-1)
g0 = itemgetter(0)
Q = sorted([inpl() for _ in range(M)], key=g0, reverse=True)
#print(*Q, sep="\n")

HQ = [(0, 0), (10**18, N)]

for i in range(N):
    while HQ[0][1] < i:
        heappop(HQ)
    v = HQ[0][0]
    while len(Q) and (i == (Q[-1][0]-1)):
        l, r, c = Q.pop()
        heappush(HQ, (v+c, r-1))


if v == 10**18:
    print(-1)
else:
    print(v)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for k in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for k in range(c)] for k in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

class SegTree:
    """
    セグメント木
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        # 初期化の値が決まっている場合
        if A:
            # 1段目(最下段)の初期化
            for i in range(n):
                self.tree[n2+i] = A[i]
            # 2段目以降の初期化
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = self.func(x, self.tree[i ^ 1])
            i >>= 1
 
    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

N, M = MAP()
LRC = []
for i in range(M):
    l, r, c = MAP()
    l -= 1
    r -= 1
    LRC.append((l, r, c))

LRC.sort()
st = SegTree(N, min, INF)
st.update(0, 0)
for l, r, c in LRC:
    mn = st.query(l, r+1)
    st.update(r, min(st.get(r), mn+c))

ans = st.get(N-1)
if ans != INF:
    print(st.get(N-1))
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import bisect

input = sys.stdin.readline

N, M = list(map(int,input().split()))
LRC = [list(map(int,input().split())) for i in range(M)]
LRC.sort()

INF = 100100100100100100
dist = [INF]*N
dist[0] = 0

for li, ri, ci in LRC:
	td = dist[li-1]+ci
	ti = bisect.bisect(dist,dist[li-1]+ci)
	ti = min(ti,ri+1)
	for i in range(ti,ri):
		dist[i] = td

ans = dist[-1]
if ans==INF: ans = -1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 998244353
inf = float('INF')

#A
def A():
    n = II()
    n -= 1
    print(n // 2)
    return

#B
def combination_mod(n, k, mod=mod):
    """ power_funcを用いて(nCk) mod p を求める """ 
    """ nCk = n!/((n-k)!k!)を使用 """

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * pow(b, mod - 2, mod) * pow(c, mod - 2, mod)) % mod
    

def B():
    n = II()
    d = LI()
    dic = defaultdict(int)
    if d[0] != 0:
        print(0)
        return
    for di in d[1:]:
        dic[di] += 1
    ans = 1
    di = list(dic.items())
    di.sort()
    if di[0][0] != 1:
        print(0)
        return
    for i in range(len(di) - 1):
        if di[i][0] != di[i + 1][0] - 1:
            print(0)
            return
    be = 1
    for _, b in di:
        ans *= pow(be, b, mod)
        be = b
        ans %= mod
    print(ans)
    return
class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
#C
def C():
    n = II()
    a = LI()
    b = LI()
    tmp = [inf, inf]
    res = None
    for i in range(n):
        if tmp[0] >= b[i] - a[i] >= 0 and b[i] < tmp[1]:
            res = i
            tmp = [b[i] - a[i], b[i]]
    if res == None:
        print("No")
        return
    del a[res]
    del b[res]
    a.sort()
    b.sort()
    ans = 0
    bit = BinaryIndexedTree(b[-1] + 1)
    n -= 1
    for i in range(n):
        tmp = bisect_right(a, b[i]) - bit.sum(b[i])
        bit.add(b[i],1)
        if tmp <= 0:
            print("No")
            return
    print("Yes")

    return

from heapq import heappush, heappop

def Dijkstra(num, start, vedge):

    dist = [float("inf") for i in range(num)]
    dist[0] = 0
    for i in range(num):
        du = dist[i]
        l = i
        for k, j in vedge[i]:
            if dist[j] <= du + k:
                continue
            for j in range(j, i - 1, -1):
                if dist[j] > du + k:
                    dist[j] = du + k
                    continue
                break
    return dist


#D
def D():
    n, m = LI()
    dist = [[] for i in range(n)]
    for _ in range(m):
        l, r, c = LI_()
        c += 1
        dist[l].append([c, r])
    for i in range(n):
        dist[i].sort()
    dist = Dijkstra(n, 0, dist)
    print(dist[n - 1] if dist[n - 1] != inf else -1)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
edge = [list(map(int, input().split())) for i in range(m)]
edge.sort()
from heapq import heappop,heapify,heappush
heapify(edge)

heap = [(0, 1)]
dist = [float("inf")]*(n+1)
while heap:
    cost, cur = heappop(heap)
    if dist[cur] <= cost:
        continue
    dist[cur] = cost
    while edge:
        if edge[0][0] <= cur:
            l,r,c = heappop(edge)
            if r < cur:
                continue
            heappush(heap,(cost+c, r))
        else:
            break

if dist[-1] == float("inf"):
    print(-1)
else:
    print(dist[-1])

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
n,m=map(int,input().split())
lrc=[list(map(int,input().split())) for i in range(m)]
lrc.sort()
# print(lrc)
li=[float('inf')]*n
li[0]=0
#####segfunc######
def segfunc(x,y):
   return min(x,y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele = float('inf')

num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
init(li)
# print(seg)
for i in range(m):
    tmp=query(lrc[i][0]-1,lrc[i][1]-1)
    tmp2=query(lrc[i][1]-1,lrc[i][1])
    if tmp2>lrc[i][2]+tmp:
        update(lrc[i][1]-1,lrc[i][2]+tmp)
    # print(seg[-num+n-2])
# print(seg)
if seg[-num+n-2]==float('inf'):
    print(-1)
else:
    print(seg[-num+n-2])

Submission status: Accepted

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()


N, M = list(map(int, input().split()))

LRC = []
for _ in range(M):
	LRC.append(tuple(map(int, input().split())))

LRC.sort()


class seg_tree():
	def __init__(self, N):
		# N: 処理する区間の長さ
		self.N0 = 2 ** (N - 1).bit_length()
		self.INF = 2 ** 100 - 1 #単位限的なもの(最小値なので、非常に大きい値を置いておく)
		self.data = [self.INF] * (2 * self.N0)

	# a_k の値を x に更新
	def update(self, k, x):
		#値は0始まり
		k += self.N0 - 1
		self.data[k] = x
		while k >= 0:
			k = (k - 1) // 2
			self.data[k] = min(self.data[2 * k + 1], self.data[2 * k + 2])

	# 区間[l, r)の最小値
	def query(self, l, r):
		L = l + self.N0
		R = r + self.N0
		s = self.INF
		while L < R:
			if R & 1:
				R -= 1
				s = min(s, self.data[R - 1])

			if L & 1:
				s = min(s, self.data[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return s

dist = seg_tree(N)
dist.update(0, 0)

for i in range(M):
	L, R, C = LRC[i]
	L -= 1
	R -= 1
	dist_start = dist.query(L, N)
	target_dist = dist.query(R, N)
	if dist_start + C < target_dist:
		dist.update(R, dist_start + C)


ans = dist.query(N - 1, N)
if ans == dist.INF:
	print(-1)
else:
	print(ans)

Submission status: Accepted

Solution code:
#D
import sys
input=sys.stdin.readline
class SegmentTree():
    def __init__(self,param,default,func):
        if isinstance(param,list):
            n=len(param)
        else:
            n=param
        self.d=default
        self.leaf=1<<(n-1).bit_length()
        if isinstance(param,list):
            self.tree=[default]*(self.leaf-1)+param+[default]*(self.leaf-n)
            for i in range(self.leaf-2,-1,-1):
                self.tree[i]=func(self.tree[i*2+1],self.tree[i*2+2])
        else:
            self.tree=[default]*(self.leaf*2-1)
        self.f=func
    def find(self,i):
        return self.tree[i+self.leaf-1]
    def update(self,idx,a):
        idx+=self.leaf-1
        self.tree[idx]=a
        while idx:
            idx=(idx-1)>>1
            self.tree[idx]=self.merge(self.tree[idx*2+1],self.tree[idx*2+2])
    def merge(self,a,b):
        return self.f(a,b)
    def get_top(self):
        return self.tree[0]
    def query(self,a,b): #[a,b)
        T=self.tree
        l,r=a+self.leaf-1,b+self.leaf-1
        res=self.d
        while l<r:
            if not l%2:
                res=self.merge(res,T[l])
                l+=1
            if not r%2:
                r-=1
                res=self.merge(res,T[r])
            l>>=1; r>>=1
        return res

def main():
    n,m=map(int,input().split())
    LRC=[list(map(int,input().split())) for _ in range(m)]
    LRC.sort()
    #print(LRC)
    seg=SegmentTree(n+1,float('inf'),min)
    seg.update(1,0)
    for l,r,c in LRC:
        a=seg.query(l,r)
        b=seg.find(r)
        k=min(a+c,b)
        seg.update(r,k)
    print(-1 if seg.find(n)==float('inf') else seg.find(n))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
lst = []
for i in range(m):
    lsti = list(map(int, input().split()))
    lst.append(lsti)

lst.sort(key= lambda x: x[2], reverse=True)
lst.sort(key= lambda x: x[0])

d = [10**18 for i in range(n+1)]
d[1] = 0
for lsti in lst:
    l = lsti[0]
    r = lsti[1]
    c = lsti[2]
    if l == 1:
        for i in range(l+1, r+1):
            d[i] = c
    else:
        for i in range(l+1, r+1):
            j = l+1+r-i
            if d[l]+c < d[j]:
                d[j] = d[l] + c
            else:
                break

if d[n] == 10**18:
    print(-1)
else:
    print(d[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
# MOD = 10**9+7
MOD = 998244353

class SegmentTree:

    def __init__(self, N):
        self.N = 1<<(N-1).bit_length()
        self.data = [None] * (2*self.N)

    # 時刻 t に [l, r) を v に変更する
    def update(self, l, r, t, v):
        L, R, val = l+self.N, r+self.N, (t, v)
        while L < R:
            if R & 1:
                R -= 1
                self.data[R-1] = val
            if L & 1:
                self.data[L-1] = val
                L += 1
            L >>= 1
            R >>= 1

    # 現在の x の値を得る
    def getValue(self, x):
        x += self.N-1
        ret = (-1, INF)
        while x >= 0:
            if self.data[x]:
                ret = max(ret, self.data[x])
            x = (x-1)//2
        return ret[1]

N, M = map(int, input().split())
es = defaultdict(list)
for i in range(M):
    l, r, c = map(int, input().split())
    es[l-1].append((c, r))
if 0 not in es:
    print(-1)
    exit()
for l in es:
    es[l].sort()
seg = SegmentTree(N)
seg.update(0, 1, 0, 0)
seg.update(1, N, 1, INF)
Time = 2
for l in range(N):
    esl = es[l]
    d = seg.getValue(l)
    for c, r in esl:
        s, t = l, r
        while s+1 < t:
            m = (s+t)//2
            if seg.getValue(m) <= d+c:
                s = m
            else:
                t = m
        seg.update(t, r, Time, d+c)
        Time += 1
ans = seg.getValue(N-1)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,M = II()
L,R,C = Line(M,3)

from heapq import heappop, heappush
def dijkstra(E,s,n):
    inf=float('inf')
    d=[inf for _ in range(n)]
    d[s]=0
    q=[]
    heappush(q,(0,s))
    while q:
        du, u1 = heappop(q)
        if d[u1]<du: continue
        for v1,weight in E[u1].items():
            alt=du+weight
            if d[v1]>alt:
                d[v1]=alt
                heappush(q, (alt,v1))
    return d

A = []
for i in range(M):
    A.append((L[i]-1,R[i]-1,C[i]))
A.sort(key=lambda x:-x[2])

E = [dict() for _ in range(N)]
for i in range(M):
    E[A[i][0]][A[i][1]] = A[i][2]

for i in range(N-1):
    E[i+1][i] = 0

d = dijkstra(E,0,N)
if d[-1]==float('inf'):
    print(-1)
else:
    print(d[-1])

Submission status: Accepted

Solution code:
# instead of AVLTree

INF = 10**14

class BIT():
    def __init__(self, max):
        self.max = max
        self.data = [INF]*(self.max+1)
    
    def update(self, i, x):
        while i > 0:
            self.data[i] = min(self.data[i], x)
            i -= i & -i

    def read(self, i):
        m = INF
        while i <= self.max:
            m = min(self.data[i], m)
            i += i & -i
        return m

import sys
input = sys.stdin.readline
from operator import itemgetter

N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
LRC.sort(key=itemgetter(0))

bit = BIT(N)
bit.update(1, 0)

for l, r, c in LRC:
    m = bit.read(l)
    bit.update(r, m+c)

ans = bit.data[N]
if ans == INF:
    print(-1)
else:
    print(ans)