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: Time Limit Exceeded

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):
    """ vedge は DAG の 重みとして vedge[from] = (to, value)　としておくこと """
    """ DAGでない場合は vedge[from] と vedge[to] の両方を作ること """
    """ dist[i] は start から i までの最短距離 """

    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        l = u
        for k, j in vedge[u]:
            if dist[j] < du + k:
                continue
            for j in range(l + 1, j + 1):
                if dist[j] > du + k:
                    dist[j] = du + k
                    heappush(q, [dist[j], j])
                    l = j
    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: Time Limit Exceeded

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):
    """ vedge は DAG の 重みとして vedge[from] = (to, value)　としておくこと """
    """ DAGでない場合は vedge[from] と vedge[to] の両方を作ること """
    """ dist[i] は start から i までの最短距離 """

    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        l = u
        for k, j in vedge[u]:
            if dist[j] < du + k:
                continue
            for j in range(l + 1, j + 1):
                if dist[j] > du + k:
                    dist[j] = du + k
                    heappush(q, [dist[j], j])
                    l = u
    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: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline
    INF = 10**15
    ans = INF
    N, M = map(int, input().split())
    heap = []
    for _ in range(M):
        l, r, c = map(int, input().split())
        heappush(heap, (l-1, r-1, c))
    
    front = []
    heappush(front, (0, 0))
    while heap:
        l, r, c = heappop(heap)

        front_ = []
        while front:
            r_, c_ = heappop(front)
            if r_ < l:
                continue
            
            heappush(front_, (r_, c_))
            heappush(front_, (r, c+c_))
            if r == N-1:
                ans = min(ans, c+c_)
        
        front = front_
            
    if ans == INF:
        return -1
    
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, m = [int(v) for v in input().split(' ')]

costs = []
links = []
for i in range(n):
    costs.append([0] * i)
    links.append(set())

for i in range(m):
    l, r, c = [int(v) for v in input().split(' ')]
    l -= 1
    r -= 1

    for j in range(l, r):
        for k in range(j + 1, r + 1):
            c0 = costs[k][j]
            if c0 == 0 or c0 > c:
                costs[k][j] = c
                links[k].add(j)

h = []
heapq.heappush(h, (0, n-1))

while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    if n0 == 0:
        print(c0)
        exit()

    for n1 in links[n0]:
        c1 = costs[n0][n1]
        heapq.heappush(h, (c0 + c1, n1))

print("-1")

Submission status: Time Limit Exceeded

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


class LazySegmentTree:
    
    def __init__(self, N, init_node=None, mode="min"):
        self.INF = 10**18
        
        if mode == "sum":
            self.aggfunc = lambda x, y: x+y
            self.lazyaddfunc = lambda x, l, r: x*(r-l)
            self.lazyfunc = lambda x: x//2
        
        elif mode == "max":
            self.aggfunc = lambda x, y: x if x > y else y
            self.lazyaddfunc = lambda x, l, r: x
            self.lazyfunc = lambda x: x
        
        elif mode == "min":
            self.aggfunc = lambda x, y: x if x > y else y
            self.lazyupdatefunc = lambda x, l, r: x
            self.lazyfunc = lambda x, y: min(x, y)
        
        self.size = 2**int.bit_length(N)
        self.node = [self.INF]*(2*self.size-1)
        if not init_node is None:
            for i in range(N):
                self.node[i+self.size-1] = init_node[i]
            for i in range(self.size-2, -1, -1):
                self.node[i] = min(self.node[2*i+1], self.node[2*i+2])
        self.lazy = [self.INF]*(2*self.size-1)
 
    def eval(self, k, l, r):
        if self.lazy[k] < self.INF:
            self.node[k] = min(self.node[k], self.lazy[k])
            if r-l-1:
                self.lazy[2*k+1] = min(self.lazy[2*k+1], self.lazy[k])
                self.lazy[2*k+2] = min(self.lazy[2*k+2], self.lazy[k])
            self.lazy[k] = self.INF*1

    def update(self, a, b, val):
        Q = [[0, 0, self.size]]
        Q2 = []
 
        def inner(k, l, r):
            nonlocal Q, Q2
            self.eval(k, l, r)
            if (b <= l) or (r <= a):
                return
            if (a<=l) and (r<=b):
                self.lazy[k] = min(self.lazy[k], val)
                self.eval(k, l, r)
            else:
                Q.append([2*k+1, l, (l+r)//2])
                Q.append([2*k+2, (l+r)//2, r])
                Q2.append(k)
 
        while Q:
            inner(*Q.pop())
        
        while Q2:
            k = Q2.pop()
            self.node[k] = min(self.node[2*k+1], self.node[2*k+2])
 
 
    def getagg(self, a, b):
        ix = 0
        Q = [[0, 0, self.size, 0]]
        Q2 = []
        S = [0]
 
        def inner(k, l, r, i):
            nonlocal ix, Q, Q2, S
            if (b<=l) or (r <= a):
                return self.INF
            self.eval(k, l, r)
            if (a<=l) and (r<=b):
                S[i] = self.node[k]
            else:
                Q.append([2*k+1, l, (l+r)//2, ix+1])
                Q.append([2*k+2, (l+r)//2, r, ix+2])
                Q2.append([ix, ix+1, ix+2])
                S.extend([0, 0])
                ix += 2
        while Q:
            inner(*Q.pop())
 
        while Q2:
            x, y, z = Q2.pop()
            S[x] = max(S[y], S[z])
        return S[0]

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

for i in range(N):
    v = LST.getagg(i, i+1)
    while len(Q) and (i == (Q[-1][0]-1)):
        l, r, c = Q.pop()
        LST.update(l-1, r, c+v)
        #print(*[LST.getagg(i, i+1) for i in range(N)], sep=" ")

ans = LST.getagg(N-1, N)
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for i in range(M)]
LRC = sorted(LRC)
#print(LRC)
A = [10**16] * N
A[0] = 0

for i in range(M):
  L, R, C = LRC[i][0] - 1, LRC[i][1] - 1, LRC[i][2]
  if C < A[R] - A[L]:
    for j in range(L+1, R+1):
      A[j] = min(A[j], A[L] + C)

#出力
ans = A[-1]
if ans > 10 ** 15:
  ans = -1
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

n,m = map(int,input().split())

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(m):
    x,y,z = map(int,input().split())
    
    for j in range(x+1,y+1):
        #print(x,j,z)
        
        if cost[x-1][j-1] != 0:
            cost[x-1][j-1] = min(z,cost[x-1][j-1])
        else:
            cost[x-1][j-1] = z
            
        if cost[j-1][x-1] != 0:
            cost[j-1][x-1] = min(z,cost[j-1][x-1])
        else:
            cost[j-1][x-1] = z
        
ans = dijkstra(0,n,m,cost)[n-1]
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
lrc = []
for i in range(m):
    lrc.append(list(map(int, input().split())))
lrc.sort(key = lambda x: (x[1], x[2]))
lrc.sort()
dis = [float("inf")] * n
dis[0] = 0
for i in range(m):
    l = lrc[i][0]
    r = lrc[i][1]
    c = lrc[i][2]
    for j in range(lrc[i][1], l, -1):
        if dis[j - 1] <= dis[l - 1] + c:
            break
        else:
            dis[j - 1] = min(dis[j - 1], dis[l - 1] + c)
if dis[n - 1] == float("inf"):
    print(-1)
else:
    print(dis[n - 1])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
edge.sort()

q = []
for l, r, c in edge:
    # print(q)

    if l == 1:
        heappush(q, (r, c))
    else:
        q2 = []
        cand = float("inf")
        while q:
            y, z = heappop(q)

            if y < l:
                continue
            elif y < r:
                cand = min(cand, z)
                heappush(q2, (y, z))
            else:
                heappush(q2, (y, z))

        if cand != float("inf"):
            heappush(q2, (r, cand + c))

        q = q2
# print(q)

if len(q) == 0:
    ans = -1
else:
    ans = -1
    for y, z in q:
        if y == n:
            if ans == -1:
                ans = z
            else:
                ans = min(ans, z)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 10
graph = [[INF] * (N+1) for _ in range(N+1)]
for i in range(N+1):
    graph[i][i] = 0
LRC.sort(key=lambda x: x[2], reverse=True)
LRC.sort()
dp = [INF] * (N+1) # dp[0]は使わない
visited = set([1])
dp[1] = 0
for l, r, c in LRC:
    if l not in visited:
        print(-1)
        exit()
    for i in range(l, r+1):
        visited.add(i)
        dp[i] = min(dp[i], dp[l]+c)
if dp[N] == INF:
    print(-1)
else:
    print(dp[N])

Submission status: Time Limit Exceeded

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):
    """ vedge は DAG の 重みとして vedge[from] = (to, value)　としておくこと """
    """ DAGでない場合は vedge[from] と vedge[to] の両方を作ること """
    """ dist[i] は start から i までの最短距離 """

    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        l = u
        for k, j in vedge[u]:
            for j in range(l + 1, j + 1):
                if dist[j] > du + k:
                    dist[j] = du + k
                    heappush(q, [dist[j], j])
                    l = u
    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: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())

ans = [-1] * (n + 1)
ll = []
for i in range(m):
    l, r, c = map(int,input().split())
    ll.append([l, r, c])
ll.sort()

for l, r, c in ll:
    if l == 1:
        for i in range(l + 1, r + 1):
            if ans[i] == -1:
                ans[i] = c
            else:
                if c < ans[i]:
                    ans[i] = c
    else:
        if ans[l] != -1:
            for i in range(l + 1, r + 1):
                if ans[i] == -1:
                    ans[i] = ans[l] + c
                else:
                    if c + ans[l] < ans[i]:
                        ans[i] = c + ans[l]
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
CM = 1000000000 * 100000 * 10

N,M = map(int, input().strip().split(" "))
LRC = []
for i in range(M):
    LRC.append(list(map(int, input().strip().split(" "))))
LRC.sort(key = lambda x:-x[2])
P = [CM] * N
P[0] = 0
while True:
    chk = False
    for l in LRC:
        for i in range(l[0], l[1]):
            if P[l[0]-1] + l[2] < P[i]:
                P[i] = P[l[0]-1] + l[2]
                chk = True
    if not chk:
        break
if P[-1] == CM:
    print(-1)
else:
    print(P[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
import heapq

# グラフの初期化
def initialize_graph():
    graph = {}
    n, edge_list = read_file()
    for edge_inf in edge_list:
        node1 = edge_inf[0]
        node2 = edge_inf[1]
        cost = edge_inf[2]
        # ノードの設定と無向エッジのコスト設定
        graph = set_new_node(graph, node1, node2)
        graph[node1][node2] = cost
        graph[node2][node1] = cost
    return n, graph

def set_new_node(graph, node1, node2):
    if not node1 in graph.keys():
        graph[node1] = {}
    if not node2 in graph.keys():
        graph[node2] = {}
    return graph

# ダイクストラ法によって最短経路問題を解く
def solve_by_dijkstra(graph, n):
    # ノード毎のSTARTからの最小コスト
    min_dist_dict = {}
    # ノードに最小コストで辿り着く場合の直前のノード
    prev_node_dict = {}
    q = []
    heapq.heappush(q, (0, 1))
    
    prev_node = ''

    while True:
        # 確定したノードから遷移可能なノードのうち
        # 最小のコストと遷移先ノードをmin_dist_dictとprev_node_dictに設定
        if q == []:
            return None, None
        dist, node = heapq.heappop(q)
        min_dist_dict[node] = dist
        prev_node_dict[node] = prev_node
        # もしGOALノードの最小コストが確定したらループを抜ける
        if node == n: 
            return min_dist_dict, prev_node_dict
        prev_node = node
        # 確定したノードから遷移可能なノードについて
        # コストを計算し，キュー(q)に追加する
        culc_min_dist_and_put(graph, q, node, min_dist_dict, prev_node_dict)
    return None, None

def culc_min_dist_and_put(graph, q, departure_node, min_dist_dict, prev_node_dict):
    # 直前に確定したノードから遷移可能なすべてのノードについて繰り返し
    for arrival_node in graph[departure_node].keys():
        # 遷移可能なノードについて，直前に確定したノードから遷移した場合のコストを計算
        tmp_d = min_dist_dict[departure_node] + graph[departure_node][arrival_node]
        # 過去に遷移先ノードの最小コストを計算済みかどうか
        if arrival_node in min_dist_dict.keys():
            # 過去に計算していたSTARTからの最小コストより直前に確定したノードから遷移した場合の
            # コストが小さかった場合，最小コストを更新
            if tmp_d < min_dist_dict[arrival_node]:
                min_dist_dict[arrival_node] = tmp_d
                heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))
        else:
            min_dist_dict[arrival_node] = tmp_d
            heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))

def main():
    n, graph = initialize_graph()
    min_dist_dict, prev_node_dict = solve_by_dijkstra(graph, n)
    #print("min_dist_dict", min_dist_dict)
    #print("prev_node_dict", prev_node_dict)
    if min_dist_dict is not None:
        # GOALノードからprev_node_dictをたどって経路を復元
        #print('Route : %d '%n,end='')
        #node = n
        #while True:
        #    if node == 1:
        #        print()
        #        break
        #    #print(' ← ' + str(prev_node_dict[node]),end='')
        #    node = prev_node_dict[node]
        out = min_dist_dict[n]
    else:
        out = -1
    #print('Min Cost : ' +  str(out))
    print(out)

def read_file():
    #file_name = 'edge_inf.csv'
    #edge_list = []
    #with open(file_name,'r',encoding='utf-8') as fin:
    #    for line in fin.readlines():
    #        edge_list.append(re.sub(r'[\r\n]','',line))

    M = 10 ** 10
    n, m = map(int, input().split(" "))
    ws = [[M for _ in range(n+1)] for _ in range(n+1)]

    pairs = []
    for _ in range(m):
        l, r, w = map(int, input().split(" "))
        #print("i", _, l, r, w)
        for s in range(l, r+1):
            for t in range(s+1, r+1):
                #print((s, t))
                ws[s][t] = min(ws[s][t], w)
                pairs.append((s, t))

    set_pairs = set(pairs)
    #print(pairs, set_pairs)
    edge_list = []
    for s, t in set_pairs:
        w = ws[s][t]
        edge_list.append([s, t, w])

    #print("edge_list", edge_list)
    return n, edge_list


if __name__ == '__main__':
    main()
    sys.exit(0)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N, M = LI()
dp = [[mod for i in range(N)] for i in range(N)]
for i in range(N):
    dp[i][i] = 0
for m in range(M):
    L,R,c = LI()
    L -= 1
    R -= 1
    for l in range(L,R):
        for r in range(l+1,R+1):
            dp[l][r] = min(dp[l][r], c)

# print(dp)
dp2 = [mod for i in range(N)]
dp2[0] = 0
for i in range(N):
    for j in range(i):
        dp2[i] = min(dp2[i], dp2[j] + dp[j][i])
if dp2[-1] == mod:
    print(-1)
else:
    print(dp2[-1])