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:
# -*- coding: utf-8 -*-
from math import atan, pi
import sys
from collections import defaultdict
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 0
            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] = self.aggfunc(S[y], S[z])
        return S[0]

N, M = inpl()
init_node = [0] + [10**18]*(N-1)
LST = LazySegmentTree(N, init_node=init_node)
Q = [inpl() for _ in range(M)]
Q = sorted(Q, key=lambda x: x[0], 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:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]

adjm = [[float('inf')] * N for _ in range(N)]

for lrc in LRC:
    l = lrc[0]-1
    r = lrc[1]-1
    c = lrc[2]

    for i in range(l, r):
        for j in range(i+1, r+1):
            if adjm[i][j] > c:
                adjm[i][j] = c
                adjm[j][i] = 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])

warshall_floyd(adjm)

res = adjm[0][N-1]
if res == float('inf'):
    print(-1)
else:
    print(res)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
d = []
for _ in range(m):
  l,r,c = map(int,input().split())
  d.append([l,r,c])
d.sort(key=lambda x:x[0])
g = [float("inf") for _ in range(n+1)]
g[1] = 0
f = 1
for i in range(m):
  if d[i][0] > f:
    print(-1)
    exit()
  f = max(f,d[i][1])
  sm = d[i][2]+g[d[i][0]]
  if g[d[i][1]] > sm:
    g[d[i][1]] = sm
    j = d[i][1]-1
    while g[j] > sm:
      g[j] = sm
      j -= 1
if g[n] != float("inf"):
  print(g[n])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
from collections import defaultdict
N,M = map(int,input().split(' '))
g = defaultdict(list)
for i in range(1,M+1):
    l,r,c= list(map(int,input().split(' ')))
    g[l].append((r,c))
    for i in range(l+1,r):
        g[r].append((i,0))

INF = 10**20
d = [INF] * (N+1)
d[1] = 0
que = []
heappush(que,(1,0))
while que:
    s, dist = heappop(que)
    if d[s] < dist:
        continue
    for t,c in g[s]:
        if d[t] > d[s] + c:
            d[t] = d[s] + c
            heappush(que,(t,d[t]))
if d[N] == INF:
    print(-1)
    exit()
print(d[N])

Submission status: Time Limit Exceeded

Solution code:
import math
N, M =map(int, input().split())
node_num = N
route_list  = [[0 for i in range(N)] for j in range(N)]

for i in range(M):
    l,r,c = map(int, input().split())
    for k in range(l,r):
      for j in range(k+1,r+1):

        if route_list[k-1][j-1] == 0:
          route_list[k-1][j-1] = c
          route_list[j-1][k-1] = c
        else:
          route_list[k-1][j-1] = min(route_list[k-1][j-1],c)
          route_list[j-1][k-1] = min(route_list[j-1][k-1],c)

unsearched_nodes = list(range(node_num)) 
distance = [float('inf')] * node_num 
previous_nodes = [-1] * node_num
distance[0] = 0

def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1
while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance =float('inf') # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance[node_index]: 
            posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_list[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新
#print("-----経路-----")
previous_node = node_num - 1
"""
while previous_node != -1:
    if previous_node !=0:
        print(str(previous_node + 1) + " <- ", end='')
    else:
        print(str(previous_node + 1))
    previous_node = previous_nodes[previous_node]
"""
#print("-----距離-----")
if distance[node_num - 1] ==float('inf'):
  print(-1)
else:
  print(distance[node_num - 1])

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    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)] 
for i in range(m):
    x,y,z = map(int,input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z
for i in range(1,n):
    cost[i][i-1]=0
x=dijkstra(0,n,m,cost)[n-1]
if x==float("inf"):
  print(-1)
else:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline
    INF = 10**15
    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))
    
    dp = [INF]*N
    dp[0] = 0
    keys = [0]
    while heap:
        l, r, c = heappop(heap)
        
        s = INF
        for k in keys:
            if k < l or k >= r:
                continue
            s = min(s, dp[k])
        dp[r] = min(dp[r], s+c)
        keys.append(r)
        
    if dp[N-1] == INF:
        return -1
    
    return dp[N-1]

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ro = [[0 for i in range(n)] for i in range(n)]
for i in range(m):
    l, r, c = map(int, input().split())
    for j in range(l-1, r-1):
        for k in range(l, r):
            if ro[j][k] == 0:
                ro[j][k] = c
                ro[k][j] = c
            else:
                if ro[j][k] > c:
                    ro[j][k] = c
                    ro[k][j] = c
             


route_list = ro

node_num = len(route_list) #ノードの数

unsearched_nodes = list(range(node_num)) # 未探索ノード
distance = [float("inf")] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0 # 初期のノードの距離は0とする

def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = float("inf") # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance[node_index]: 
            posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_list[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

n, m = map(int, raw_input().split())
graph = {}
for _ in range(m):
    l, r, c = map(int, raw_input().split())
    for s in range(l, r + 1):
        for e in range(s + 1, r + 1):
            if s not in graph:
                graph[s] = {e: c}
            elif e not in graph[s]:
                graph[s][e] = c
            else:
                graph[s][e] = min(graph[s][e], c)

start = 1
dist = defaultdict(lambda: float('inf'))
dist[start] = 0
prev = defaultdict(lambda: None)
queue = []
heappush(queue, (dist[start], start))

while queue:
    dist_u, u = heappop(queue)
    if dist[u] < dist_u:
        continue
    if u not in graph:
        break
    for v, weight in graph[u].items():
        alt = dist_u + weight
        if dist[v] > alt:
            dist[v] = alt
            prev[v] = u
            heappush(queue, (alt, v))

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

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
import heapq
N, M = map(int, input().split())
dp = [[float('inf')] * (N+1) for _ in range(N+1)]
for i in range(1+N):
    dp[i][i] = 0
for _ in range(M):
    l, r, c = map(int, input().split())
    for i in range(l, r+1):
        for j in range(i+1, r+1):
            dp[i][j] = min(dp[i][j], c)
            dp[j][i] = min(dp[j][i], c)
visited = set()
q = [(0, 1)]
while q:
    dis, idx = heapq.heappop(q)
    if idx == N:
        print(dis)
        exit()
    if idx in visited:  continue
    visited.add(idx)
    for u in range(1, N+1):
        if u != idx and dp[idx][u] != float('inf'):
            heapq.heappush(q, (dis+dp[idx][u], u))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from operator import itemgetter

N, M = map(int, input().split())
LRC = []

D = np.array([float('Inf')] * (N+1))
D[1] = 0

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

LRC.sort(key=itemgetter(1))

for m in range(M):
    l, r, c = LRC[m][0], LRC[m][1], LRC[m][2]
    for a in range(l+1, r+1):
        if D[a] > D[l] + c:
            D[a:r+1] = D[l] + c
            break

if D[N] < float('Inf'):
    print(int(D[N]))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

n,m=LI()
edge=[[] for _ in range(n)]

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

for i in range(m):
  l,r,c=LI()
  for i in range(l-1,r-1):
    for j in range(i+1,r):
      edge[i].append([c,j])
      edge[j].append([c,i])

ans=dijkstra_heap(n,0,edge)
if ans[-1]==inf:
  print(-1)
  exit()
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
N,M = [int(x) for x in input().split()]
LRC = [[int(x) for x in input().split()] for _ in range(M)]
LRC.sort(key=itemgetter(0))
dist = [float('inf')] * N
dist[0] = 0
for l,r,c in LRC:
    fr = min(dist[l-1:r])
    for x in range(l-1,r):
        dist[x] = min(dist[x], fr+c)

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().strip().split())
LRC = [list(map(int, input().strip().split())) for i in range(M)]
LRC.sort()
LRC = sorted(LRC, key=lambda h: (h[0], h[2]))
#print(LRC)

max_end = 1
tf = True
for lrc in LRC:
    if lrc[0] > max_end:
        tf = False
        break
    max_end = max(max_end, lrc[1])

if not(tf) or max_end < N:
    print(-1)
else:
    INF = -1
    dp = [INF] * (N+1)
    dp[1] = 0
    for lrc in LRC:
        for i in range(lrc[0], lrc[1]+1):
            if i == 0:
                continue
            if dp[i] == INF:
                dp[i] = dp[lrc[0]] + lrc[2]
            else:
                dp[i] = min(dp[lrc[0]] + lrc[2], dp[i])
    #print(dp)
    print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

n,m=LI()
edge=[[] for _ in range(n)]

def dijkstra_heap(n,s):
  #始点sから各頂点への最短距離
  d = [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

for i in range(m):
  l,r,c=LI()
  for i in range(l-1,r-1):
    for j in range(i+1,r):
      edge[i].append([c,j])
      edge[j].append([c,i])

ans=dijkstra_heap(n,0)
if ans[-1]==inf:
  print(-1)
  exit()
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

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

mx = 10**15
ss = SegTree([0] + [mx] * n, n+1, mx, min)
for l, r, c in xs:
    mm = ss.query(l, n+1)
    nx = min(mm + c, ss.query(r, r+1))
    ss.update(r, nx)
r = ss.query(n-1,n)
print(r if r != mx else -1)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]

adjm = [[float('inf')] * N for _ in range(N)]

for lrc in LRC:
    l = lrc[0]-1
    r = lrc[1]-1
    c = lrc[2]

    for i in range(l, r):
        for j in range(i+1, r+1):
            if adjm[i][j] > c:
                adjm[i][j] = c
                adjm[j][i] = 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])

adjm = floyd_warshall(adjm)

res = adjm[0][N-1]
if res == float('inf'):
    print(-1)
else:
    print(int(res))

Submission status: Time Limit Exceeded

Solution code:
INF = 10e15
N, M = map(int, input().split())
LRC = [tuple(map(int, input().split())) for _ in range(M)]
LRC.sort()
# print(LRC)

dp = [INF] * N
dp[0] = 0

for i in range(M):
    l, r, c = LRC[i]
    l -= 1
    r -= 1
    # print(l, r, c)
    if dp[l] == INF:
        continue
    for i in range(l+1, r+1):
        dp[i] = min(dp[i], dp[l] + c)

# print(dp)
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ro = [[0 for i in range(n)] for i in range(n)]
for i in range(m):
    l, r, c = map(int, input().split())
    for j in range(l-1, r-1):
        for k in range(l, r):
            if ro[j][k] == 0:
                ro[j][k] = c
                ro[k][j] = c
            else:
                if ro[j][k] > c:
                    ro[j][k] = c
                    ro[k][j] = c
             


import math

route_list = ro

node_num = len(route_list) #ノードの数

unsearched_nodes = list(range(node_num)) # 未探索ノード
distance = [float("inf")] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0 # 初期のノードの距離は0とする

def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = float("inf") # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance[node_index]: 
            posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_list[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline
    INF = 10**15
    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))
    
    dp = [INF]*N
    dp[0] = 0
    while heap:
        l, r, c = heappop(heap)
        
        s = min(dp[l:r])
        dp[r] = min(dp[r], s+c)
        
    if dp[N-1] == INF:
        return -1
    
    return dp[N-1]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush

inf = float('inf')
N, M = [int(x) for x in sys.stdin.readline().split()]
LRC = []
for _ in range(M):
    LRC.append([int(x) for x in sys.stdin.readline().split()])

dist = [inf] * N
dist[0] = 0

routes = [None] * N
for i in range(N):
    routes[i] = [inf] * N

for l, r, c in LRC:
    for i in range(l - 1, r - 1):
        for j in range(i + 1, r):
            routes[i][j] = min(routes[i][j], c)
            routes[j][i] = min(routes[j][i], c)

q = []
heappush(q, (dist[0], 0))

while q:
    d, u = heappop(q)
    if dist[u] < d:
        continue
    for i, w in enumerate(routes[u]):
        t = d + w
        if t < dist[i]:
            dist[i] = t
            heappush(q, (t, i))

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M=map(int,input().split())
A=np.array([float('inf')]*N)

T=[]
for i in range(M):
	a,b,c=map(int,input().split())
	a-=1
	b-=1
	T.append([b,a,c])
T.sort()

A[0]=0
for t in T:
	k = A[t[1]:t[0]].min()
	if k!=float('inf'):
		A[t[0]] = min(A[t[0]], k + t[2])

if A[-1]!=float('inf'):
	print(int(A[-1]))
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
LRC = list(list(map(int,input().split()))for i in range(M))
LRC.sort()
DP = [float('inf')]*N
DP[0] = 0
R = 0
for l,r,c in LRC:
    l -= 1
    r -= 1
    for i in range(l+1,r+1):
        DP[i] = min(DP[l]+c,DP[i])

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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
 
list1 = [[1,5,3], [6,4,8], [9,11,2]]
list1.sort(key=itemgetter(1))


N, M = map(int, input().split())
LRC = []

D = [float('Inf')] * (N+1)
D[1] = 0

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

LRC.sort(key=itemgetter(1))

for m in range(M):
    l, r, c = LRC[m][0], LRC[m][1], LRC[m][2]
    for a in range(l+1, r+1):
        if D[a] > D[l] + c:
            D[a] = D[l] + c

if D[N] < float('Inf'):
    print(D[N])
else:
    print(-1)

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**20] * N
A[0] = 0

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]

adjm = [[float('inf')] * N for _ in range(N)]

for lrc in LRC:
    l = lrc[0]-1
    r = lrc[1]-1
    c = lrc[2]

    for i in range(l, r):
        for j in range(i+1, r+1):
            if adjm[i][j] > c:
                adjm[i][j] = c
                adjm[j][i] = 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])

warshall_floyd(adjm)

res = adjm[0][N-1]
if res == float('inf'):
    print(-1)
else:
    print(res)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split(' '))
LRC = []
for i in [0]*M:
    l,r,c= list(map(int,input().split(' ')))
    LRC.append((l,r,c))

INF = 10**20
d = [INF] * (N+1)
d[1] = 0
for i in range(2,N+1):
    for l,r,c in LRC:
        if not (l <= i <= r):
            continue
        for n in range(l,i):
            d[i] = min(d[n]+c, d[i])
if d[N] == INF:
    print(-1)
    exit()
print(d[N])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

edges = [list(map(int, input().split())) for _ in range(m)]
edges.sort(key = lambda x: (x[0], x[1]))

dp = np.full(n + 1, np.inf)
dp[1] = 0

for e in edges:
    dp[e[0]:(e[1] + 1)] = np.minimum(min(dp[e[0]:(e[1] + 1)]) + e[2], dp[e[0]:(e[1] + 1)])

if np.isinf(dp[-1]):
    print(-1)
else:
    print(int(dp[-1]))

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])
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(l + 1, r + 1):
        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:
import sys
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline
    INF = 10**15
    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))
    
    dp = [INF]*N
    dp[0] = 0
    while heap:
        l, r, c = heappop(heap)
        if dp[l] == INF:
            return -1
        
        for i in range(l+1, r+1):
            dp[i] = min(dp[i], dp[l] + c)
        
    if dp[N-1] == INF:
        return -1
    
    return dp[N-1]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_right

n, m = li()
lrc = [list(li()) for _ in range(m)]

# n = 10**5
# m = 10**5
# lrc = [[1, n, 5] for _ in range(m)]

# l -> r の降順にソート
lrc = sorted(lrc, key=lambda x: x[2])
lrc = sorted(lrc, key=lambda x: x[1])
lrc = sorted(lrc, key=lambda x: x[0])
#lrc = sorted((sorted(lrc, key=lambda x: x[1])), key=lambda x: x[0])

# 二分探索で距離更新
INF = float('inf')
dist = [INF]*n
dist[0] = 0

for left_idx, right_idx, ci in lrc:
    left_idx -= 1
    newleft_idx = bisect_right(dist, dist[left_idx] + ci)
    for idx in range(newleft_idx, right_idx):
        dist[idx] = dist[left_idx] + ci

if dist[-1] == INF:
    print(-1)
else:
    print(dist[-1])

Submission status: Time Limit Exceeded

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

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

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

    for j in range(l, r):
        j1 = j - 1
        for k in range(j + 1, r + 1):
            k1 = k - 1
            c0 = costs[k1][j1]
            if c0 == 0 or c0 > c:
                costs[k1][j1] = c

                links[k1].append(j1)
                links[j1].append(k1)

import heapq
h = []
closed = 0

heapq.heappush(h, (0, n-1))

while len(h) > 0:
    c0, n1 = heapq.heappop(h)
    closed |= (1 << n1)

    if n1 == 0:
        print(c0)
        exit()

    for i in links[n1]:
        if closed & (1 << i) != 0:
            continue

        c1 = 0
        if i < n1:
            c1 = costs[n1][i]
        elif i > n1:
            c1 = costs[i][n1]
        if c1 > 0:
            heapq.heappush(h, (c0 + c1, i))

print("-1")