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:
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

for _ in range(m):
    _from, to, dist = map(int, input().split())
    edges[_from-1][to-1] = dist

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

G = csgraph_from_dense(edges, null_value=float('INF'))
D = dijkstra(G, directed=True, indices=0)
ans = D[-1]
if ans == float('INF'):
    ans = -1
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from heapq import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    to = defaultdict(list)
    n, m = map(int, input().split())
    for _ in range(m):
        l, r, c = map(int, input().split())
        l, r = l - 1, r - 1
        to[l].append([r, c])
    costs = [-1] * n
    hp = []
    heappush(hp, [0, 0])
    while hp:
        #print(hp)
        c, u = heappop(hp)
        if u == n - 1:
            print(c)
            #print(costs)
            exit()
        if costs[u] != -1: continue
        costs[u] = c
        for v, dc in to[u]:
            if costs[v] != -1: continue
            heappush(hp, [c + dc, v])
            for w in range(v - 1, u, -1):
                if costs[w] != -1: break
                heappush(hp, [c + dc, w])

    print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from heapq import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    to = defaultdict(list)
    n, m = map(int, input().split())
    for _ in range(m):
        l, r, c = map(int, input().split())
        l, r = l - 1, r - 1
        to[l].append([r, c])
    costs = [-1] * n
    hp = []
    heappush(hp, [0, 0])
    while hp:
        #print(hp)
        c, u = heappop(hp)
        if u == n - 1:
            print(c)
            #print(costs)
            exit()
        if costs[u] != -1: continue
        costs[u] = c
        for v, dc in to[u]:
            if costs[v] != -1: continue
            heappush(hp, [c + dc, v])
            for w in range(v - 1, u, -1):
                if costs[w] != -1: continue
                heappush(hp, [c + dc, w])

    print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
n,m,*t=map(int,open(0).read().split())
d=[0,0]+[1e18]*n
for l,r,c in sorted(zip(*[iter(t)]*3)):
 for i in range(r,l,-1):
  if d[l]+c<d[i]:d[i]=d[l]+c
  else:break
print(-(d[-2]>1e17)or d[-2])

Submission status: Time Limit Exceeded

Solution code:
n,m,*t=map(int,open(0).read().split())
d=[0,0]+[1e18]*n
for l,r,c in sorted(zip(*[iter(t)]*3)):
 for i in range(r,l,-1):d[i]=min(d[i],d[l]+c)
print(-(d[-2]>1e17)or d[-2])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
matrix = [[0] * (N+1) for i in range(N+1)]
min_distance = [0] * (N+1)
for i in range(M):
    L, R, C = map(int, input().split())
    for l in range(L,R):
        for r in range(l+1, R+1):
            if matrix[l][r] != 0:
                now = matrix[l][r]
                matrix[l][r] = min(now, C)
            else:
                matrix[l][r] = C
# print(matrix)

for i in range(1, N+1):
    for j in range(1, i):
        if min_distance[i] != 0 and matrix[j][i] != 0 and min_distance[j] != 0:
            min_distance[i] = min(min_distance[j] + matrix[j][i], min_distance[i])
        elif min_distance[i] == 0 and matrix[j][i] != 0 and min_distance[j] > 0:
            min_distance[i] = min_distance[j] + matrix[j][i]
        elif min_distance[i] == 0 and matrix[j][i] != 0 and j == 1:
            min_distance[i] = matrix[j][i]
        # print(i, j, min_distance[j], matrix[j][i], min_distance[i])

if min_distance[-1] == 0:
    print(-1)
else:
    print(min_distance[-1])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
*u,=range(n+1)
a=csgraph.johnson(csr_matrix(([0]*n+t[3::3],(u[1:]+t[1::3],u[:-1]+t[2::3])),[n+1]*2),1,1)[n]
print(int(a)if a<1e18else-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

class SegTreeMin:
    def __init__(self, n, inf=10 ** 15):
        self.n = n
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [inf] * (n2 << 1)
        self.inf = inf
        
    def update(self, i, x):
        i += self.n2
        self.tree[i] = x
        while i > 1:
            x = min(x, self.tree[i ^ 1])
            self.tree[i >> 1] = x
            i >>= 1
            
    def get_min(self, a, b):
        result = self.inf
        q = [(1, 0, self.n2)]
        while q:
            k, l, r = q.pop()
            if a <= l and r <= b:
                result = min(result, self.tree[k])
                continue
                
            m = (l + r) // 2
            k <<= 1
            if a < m and l < b:
                q.append((k, l, m))
            if a < r and l < m:
                q.append((k + 1, m, r))
                
        return result

INF = float("inf")
seg_tree = SegTreeMin(N, INF)
seg_tree.update(0, 0)
X.sort()
for l, r, c in X:
    l -= 1
    r -= 1
    tmp = seg_tree.get_min(l, r)
    seg_tree.update(r, min(tmp + c, seg_tree.get_min(r, r + 1)))
ans = seg_tree.get_min(N - 1, N)
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

class SegTreeMin:
    def __init__(self, n, inf=10 ** 15):
        self.n = n
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [inf] * (n2 << 1)
        self.inf = inf
        
    def update(self, i, x):
        i += self.n2
        self.tree[i] = x
        while i > 1:
            x = min(x, self.tree[i ^ 1])
            self.tree[i >> 1] = x
            i >>= 1
            
    def get_min(self, a, b):
        result = self.inf
        q = [(1, 0, self.n2)]
        while q:
            k, l, r = q.pop()
            if a <= l and r <= b:
                result = min(result, self.tree[k])
                continue
                
            m = (l + r) // 2
            k <<= 1
            if a < m and l < b:
                q.append((k, l, m))
            if a < r and l < m:
                q.append((k + 1, m, r))
                
        return result

INF = 10 ** 15
seg_tree = SegTreeMin(N, INF)
seg_tree.update(0, 0)
X.sort()
for l, r, c in X:
    l -= 1
    r -= 1
    tmp = seg_tree.get_min(l, r)
    seg_tree.update(r, min(tmp + c, seg_tree.get_min(r, r + 1)))
ans = seg_tree.get_min(N - 1, N)
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())

C=[[10**14]*N for i in range(N)]

for i in range(M):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    temp=[]
    for i in range(l,r):
        for j in range(i+1,r+1):
            C[i][j]=min(C[i][j],d)

DP=[10**14]*N

DP[0]=0
temp=[]

for i in range(1,N):
    for j in range(0,i):
        temp.append(DP[j]+C[j][i])
    DP[i]=min(temp)
    temp=[]

if DP[N-1]>=10**14:
    print(-1)
else:
    print(DP[N-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())

C=[[10**14]*N for i in range(N)]

D=[]
for i in range(M):
    D.append(list(map(int,input().split())))

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

for l,r,d in D:
    l-=1
    r-=1
    for i in range(l,r):
        for j in range(i+1,r+1):
            C[i][j]=d

DP=[10**14]*N

DP[0]=0
temp=[]

for i in range(1,N):
    for j in range(0,i):
        temp.append(DP[j]+C[j][i])
    DP[i]=min(temp)
    temp=[]

if DP[N-1]>=10**14:
    print(-1)
else:
    print(DP[N-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, input().split())
LRC = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: (x[0], x[1]))
 
inf = float('inf')
dp = np.full(N+1, inf)
dp[1] = 0
for l, r, c in LRC:
    dp[l:r+1] = np.minimum(dp[l:r+1], dp[l] + c)
 
if dp[-1] < inf:
    print(int(dp[-1]))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


class SegmentTree:
    def __init__(self, n, ide_ele, op, init_val=[]):
        self.n = 2 ** (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.op = op
        self.seg = [ide_ele] * 2 * self.n
        if init_val:
            for i in range(n):
                self.seg[i + self.n - 1] = init_val[i]
            for i in range(self.n - 2, -1, -1):
                self.seg[i] = self.op(self.seg[2 * i + 1], self.seg[2 * i + 2])

    def update(self, k, x):
        k += self.n - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.op(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, p, q):
        # qは含まない
        if q <= p:
            return self.ide_ele
        p += self.n - 1
        q += self.n - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self.op(res, self.seg[p])
            if q & 1 == 1:
                res = self.op(res, self.seg[q])
            p = p // 2
            q = (q - 2) // 2
        if p == q:
            res = self.op(res, self.seg[p])
        else:
            res = self.op(self.seg[p], self.op(res, self.seg[q]))
        return res

    def display(self):
        return self.seg[self.n - 1: -1]

    def query_point(self, p):
        return self.seg[p + self.n - 1]


n, m = LI()
lrc_list = sorted(LIR(m))
st = SegmentTree(n, INF, min)
st.update(0, 0)
for l, r, c in lrc_list:
    l_dist = st.query(l - 1, r)
    st.update(r - 1, min(st.query_point(r - 1), l_dist + c))
    dis = st.display()

if st.query_point(n - 1) == INF:
    print(-1)
else:
    print(st.query_point(n - 1))

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in rawData(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

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

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

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

LRC = []
for _ in range(M):
    L, R, C = map(int, input().split())
    L -= 1
    LRC.append((L, R, C))
LRC.sort()

tree = MinSegTree(N)
tree.update(0, 0)
for l, r, c in LRC:
    newDist = tree.query(l, r) + c
    oldDist = tree.query(r - 1, r)
    if newDist < oldDist:
        tree.update(r - 1, newDist)

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

Submission status: Time Limit Exceeded

Solution code:
N,M = (int(i) for i in input().split())
LRC = []

for i in range(M):
  LRC.append([int(i) for i in input().split()])

LRC.sort()

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

for i in range(M):
  for j in range(LRC[i][0],LRC[i][1]+1):
    if LRC[i][0] == 1:
      # 1から飛べる範囲を設定
      if costs[j] == -1:
        costs[j] = LRC[i][2]
      else:
        costs[j] = min(costs[j],LRC[i][2])
    else:
      # そこまでに飛べる最小コストを調べ、そのコスト+現在のコストを行う
      min_costs = -1
      for k in range(LRC[i][0],j):
        if costs[k] >= 0:
          if min_costs == -1:
            min_costs = costs[k]
          else:
            min_costs = min(min_costs,costs[k])

      if min_costs != -1 and costs[j] == -1:
        costs[j] = min_costs + LRC[i][2]
      elif min_costs != -1 and costs[j] != -1:
        costs[j] = min(costs[j],min_costs + LRC[i][2])

ans = costs[N]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = float("inf")


class SegTree():
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.data = [ele_id] * (2 * self.n - 1)
        self.ele_id = ele_id
        self.operation_func = operation_func

    def __getitem__(self, idx):
        return self.data[idx + self.n - 1]

    def update_all(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.operation_func(self.data[2 * i + 1],
                                               self.data[2 * i + 2])

    def update(self, idx, x):
        # idx番目の要素をxに更新する
        idx += self.n - 1
        self.data[idx] = x
        while idx > 0:
            idx = (idx - 1) // 2
            self.data[idx] = self.operation_func(self.data[2 * idx + 1],
                                                 self.data[2 * idx + 2])

    def query(self, a, b):
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        # [a, b)の最小値を求める
        if r <= a or b <= l:
            # [a, b)が[l, r)と交差しない
            return self.ele_id

        if a <= l and r <= b:
            # [a, b)が[l, r)を完全に含む
            return self.data[k]
        else:
            # [a, b)と[l, r)は一部被る
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.operation_func(child_l, child_r)


n, m = map(int, input().split())
l_dict = [[] for _ in range(n)]
r_dict = [[] for _ in range(n)]
edge = []
for i in range(m):
    l, r, c = map(int, input().split())
    l -= 1
    r -= 1
    l_dict[l].append(i)
    r_dict[r].append(i)
    edge.append((l, r, c))

dp = [INF] * n
dp[0] = 0
seg_rmq = SegTree(n, INF, min)
seg_rmq.update(0, 0)

for i in range(1, n):
    for j in r_dict[i]:
        l, r, c = edge[j]
        tmp = seg_rmq.query(l, r)
        dp[i] = min(dp[i], tmp + c)

    seg_rmq.update(i, dp[i])

ans = dp[-1] if dp[-1] != INF else -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Rmq:
    # 平方分割
    # 値を変更すると元のリストの値も書き換わる
    def __init__(self, a, sqrt_n=500):
        from itertools import zip_longest
        self.n = len(a)
        self.sqrt_n = sqrt_n
        self.layer1 = a
        self.layer0 = [min(values) for values in zip_longest(*[iter(a)]*sqrt_n, fillvalue=float("inf"))]

    def get_min(self, l, r):
        sqrt_n = self.sqrt_n
        parent_l, parent_r = l//sqrt_n+1, (r+1)//sqrt_n
        if parent_l < parent_r:
            return min(min(self.layer0[parent_l:parent_r]),
                       min(self.layer1[l:parent_l*sqrt_n]),
                       min(self.layer1[parent_r*sqrt_n:r]))
        else:
            return min(self.layer1[l:r])

    def set_value(self, idx, val):
        self.layer1[idx] = val
        idx //= self.sqrt_n
        self.layer0[idx] = min(self.layer0[idx], val)

    def chmin(self, idx, val):
        if self.layer1[idx] > val:
            self.set_value(idx, val)

    def debug(self):
        print("layer0=", self.layer0)
        print("layer1=", self.layer1)

    def __getitem__(self, item):
        return self.layer1[item]

    def __setitem__(self, key, value):
        self.set_value(key, value)


from operator import itemgetter
import sys

def main():
    N, M = map(int, input().split())
    LRC = list(zip(*[iter(map(int, sys.stdin.read().split()))]*3))
    LRC.sort(key=itemgetter(0))
    idx_LRC = 0

    rmq = Rmq([float("inf")] * (N+1))
    rmq.set_value(1, 0)
    for v in range(1, N+1):
        d = rmq.get_min(v, N+1)
        while idx_LRC < M:
            l, r, c = LRC[idx_LRC]
            if l <= v:
                rmq.chmin(r, d+c)
                idx_LRC += 1
            else:
                break
    ans = rmq[N]
    print(ans if ans != float("inf") else -1)

main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8357999 を
# 平方分割に書き換えた

class Rmq:
    # 平方分割
    # 値を変更すると元のリストの値も書き換わる
    def __init__(self, a, sqrt_n=500):
        from itertools import zip_longest
        self.n = len(a)
        self.sqrt_n = sqrt_n
        self.layer1 = a
        self.layer0 = [min(values) for values in zip_longest(*[iter(a)]*sqrt_n, fillvalue=float("inf"))]

    def get_min(self, l, r):
        sqrt_n = self.sqrt_n
        parent_l, parent_r = l//sqrt_n+1, (r+1)//sqrt_n
        if parent_l < parent_r:
            return min(min(self.layer0[parent_l:parent_r]),
                       min(self.layer1[l:parent_l*sqrt_n]),
                       min(self.layer1[parent_r*sqrt_n:r]))
        else:
            return min(self.layer1[l:r])

    def set_value(self, idx, val):
        self.layer1[idx] = val
        idx //= self.sqrt_n
        self.layer0[idx] = min(self.layer0[idx], val)

    def chmin(self, idx, val):
        if self.layer1[idx] > val:
            self.set_value(idx, val)

    def debug(self):
        print("layer0=", self.layer0)
        print("layer1=", self.layer1)

    def __getitem__(self, item):
        return self.layer1[item]

    def __setitem__(self, key, value):
        self.set_value(key, value)


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))

idx_LRC = 0
q = []

rmq = Rmq([float("inf")] * (N+1))

rmq.set_value(1, 0)
for v in range(1, N+1):
    d = rmq.get_min(v, N+1)
    while idx_LRC < M:
        l, r, c = LRC[idx_LRC]
        if l <= v:
            rmq.chmin(r, d+c)
            idx_LRC += 1
        else:
            break
ans = rmq[N]
print(ans if ans != float("inf") else -1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = map(int, input().split())
tail = []
head = []
cost = []
for _ in range(m):
  l, r, c = map(int, input().split())
  tail.append(l - 1)
  head.append(r - 1)
  cost.append(c)
tail += list(range(1, n))
head += list(range(n - 1))
cost += [0] * (n - 1)

tail = np.array(tail, dtype=np.int)
head = np.array(head, dtype=np.int)
cost = np.array(cost, dtype=np.int)

inf = cost.sum() + 1
dp = np.ones(n, dtype=np.int) * inf
dp[0] = 0
act = 0
unexplr = np.ones(n, dtype=np.bool)
unexplr[0] = False
while unexplr[-1]:
  edge = (tail == act)
  dp[head[edge]] = np.minimum(dp[head[edge]], dp[act] + cost[edge])
  tmp = np.ones(n, dtype=np.int) * inf
  tmp[unexplr] = dp[unexplr]
  act = tmp.argmin()
  unexplr[act] = False
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra

def solve(N: int, M: int, L: "List[int]", R: "List[int]", C: "List[int]"):
    matrix = [[float('inf')]*N for _ in range(N)]

    for i in range(M):
        matrix[L[i]-1][R[i]-1] = C[i]

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

    csr = csgraph_from_dense(matrix, null_value=float('inf'))
    dist_matrix = dijkstra(csr,directed=True,indices=0)

    if dist_matrix[-1] == float('inf'):
        print(-1)
    else:
        print(int(dist_matrix[-1]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, L, R, C)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
tail = []
head = []
cost = []
for _ in range(m):
  l, r, c = map(int, input().split())
  tail.append(l - 1)
  head.append(r - 1)
  cost.append(c)
tail += list(range(1, n))
head += list(range(n - 1))
cost += [0] * (n - 1)

inf = sum(cost) + 1
dp = [0] + [inf] * (n - 1)
act = 0
unexplr = [False] + [True] * (n - 1)
while unexplr[-1]:
  for edge in range(m + n - 1):
    to = head[edge]
    if act == tail[edge] and unexplr[to]:
      if dp[to] > dp[act] + cost[edge]:
        dp[to] = dp[act] + cost[edge]
  short = inf
  for vertex in range(n):
    if unexplr[vertex] and dp[vertex] < short:
      act = vertex
      short = dp[vertex]
  unexplr[act] = False
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
LRC = [tuple(map(int,input().split())) for i in range(M)]
LRC.sort()

INF = float('inf')
class SegTreeMin:
    def __init__(self,arr):
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [INF]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = min(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    # thanks
    # https://smijake3.hatenablog.com/entry/2018/11/03/100133
    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = min(self.nodes[2*i+1], self.nodes[2*i+2])

    def query(self,l,r):
        L = l + self.n; R = r + self.n
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.nodes[R-1])
            if L & 1:
                s = min(s, self.nodes[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

segt = SegTreeMin([0] + [INF]*N)
for l,r,c in LRC:
    mn = segt.query(l-1,r-1)
    org = segt.query(r-1,r)
    if org > mn+c:
        segt.update(r-1, mn+c)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = map(int, input().split())
edge_l = []
edge_r = []
edge_c = []
for _ in range(m):
  l, r, c = map(int, input().split())
  edge_l.append(l - 1)
  edge_r.append(r - 1)
  edge_c.append(c)
l = np.array(edge_l, dtype=np.int)
r = np.array(edge_r, dtype=np.int)
c = np.array(edge_c, dtype=np.int)

dp = np.ones(n, dtype=np.int) * (c.sum() + 1)
dp[0] = 0
active = np.zeros(n, dtype=np.bool)
active[0] = True
while np.any(active[:-1]):
  act = active.argmax()
  use = (l <= act) * (r > act)
  dp[r[use]] = np.minimum(dp[act] + c[use], dp[r[use]])
  active[r[use]] = True
if active[-1]:
  print(dp[-1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
NN = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(i+1,N):
        NN[i][j] = float("inf")
for i in range(M):
    l, r, c = map(int, input().split())
    NN[l-1][r-1] = c
    
def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d = warshall_floyd(NN)

if d[0][N-1] == float("inf"):
    print(-1)
else:
    print(int(d[0][N-1]))

Submission status: Time Limit Exceeded

Solution code:
import operator
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

class SegmentTree:
    # http://tsutaj.hatenablog.com/entry/2017/03/29/204841
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        # size 以上である最小の 2 冪を size とする
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i=None, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        if to_i is None:
            to_i = from_i + 1
        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


N, M = list(map(int, sys.stdin.readline().split()))
LRC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

LRC.sort()
LRC = [(l - 1, r - 1, c) for l, r, c in LRC]
i = 0

# dp[pos]: pos までの最短距離
dp = SegmentTree(N, fn=min, initial_values=[INF] * N)
dp.set(0, 0)
for pos in range(N):
    d = dp.get(pos, N)
    while i < M and LRC[i][0] == pos:
        l, r, c = LRC[i]
        dp.set(r, min(d + c, dp.get(r)))
        i += 1
ans = dp.get(N - 1)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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


def dijkstra(s, n, edge):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    for e in edge[s]:
        heapq.heappush(q, e)
    while q:
        minedge = heapq.heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue
        d[v] = minedge[0]
        for e in edge[v]:
            heapq.heappush(q, [e[0]+d[v], e[1]])
    return d


N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    s, t, c = map(int, input().split())
    E[s-1].append([c, t-1])
for i in range(N-1):
    E[i+1].append([0, i])

A = dijkstra(0, N, E)

ans = A[N-1]
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10**100
N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

for i in range(M):
    L, R, C = map(int, input().split())
    G[L-1].append([R-1, C])

S = 0

def dijkstra(N, S):
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] # ノード
        dis = q[0] # 過去に更新された最短距離

        # vまで2番目に短い距離（最新）　＜　過去最短距離　の時、
        # キューから取り出した過去のものを無視する
        if d[ver] < dis:
            continue

        # 隣接リストに対してループ
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

ans = dijkstra(N, S)
if ans == INF:
    print(-1)
else:
    print(dijkstra(N, S))