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:
N, M = map(int, input().split())
route_list = [[10**9 + 1] * N for _ in range(N)]
for i in range(M):
    L, R, C = map(int, input().split())
    for j in range(L, R):
        for l in range(j+1, R+1):
            route_list[j-1][l-1] = min(C, route_list[j-1][l-1])
unsearched_nodes = list(range(N))
node_num = N
distance = [10**9] * 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 = 10**9
    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)
    unsearched_nodes.remove(target_min_index)

    target_edge = route_list[target_min_index]
    for index, route_dis in enumerate(target_edge):
        if route_dis <= 10**9:
            if distance[index] > (distance[target_min_index] + route_dis):
                distance[index] = distance[target_min_index] + route_dis
                previous_nodes[index] = target_min_index

if distance[node_num - 1] == 10**9:
	print(-1)
else:
    print(distance[node_num - 1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
lrc_list = []
for _ in range(M):
    lrc_list.append(tuple(map(int, input().split())))
lrc_list.sort()
way = [float('inf')] * N
way[0] = 0
for lrc in lrc_list:
    for i in range(lrc[0], lrc[1]):
        way[i] = min(way[i], way[lrc[0] - 1] + lrc[2])

if way[N - 1] != float('inf'):
    print(way[N - 1])
else:
    print(-1)

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))
closed = n
while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    if closed <= n0:
        continue
    closed = n0
    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:
N,M=map(int,input().split())
datas=list(list(map(int,input().split())) for _ in range(M))
i1=0
i2=1
while i1!=i2:
  i1=i2
  i2=max(data[1] if data[0]<=i1 else 0 for data in datas)
if i2 != N:
  print(-1)
else:
  maximum=sum(data[2] for data in datas)
  shortest_path=list(list(0 for _1 in range(N)) for _2 in range(N))
  for i in range(N-2,-1,-1):
      shortest_path[i+1][i]=min(data[2] if data[0]<=i+1<data[1] else maximum for data in datas)
      for j in range(i+2,N,1):
          shortest_path[j][i]=min(min(data[2] if data[0]<=i+1 and j+1<=data[1] else maximum for data in datas),min(shortest_path[k][i]+shortest_path[j][k] for k in range(i+1,j,1)))
  print(shortest_path[N-1][0])

Submission status: Time Limit Exceeded

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


def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    A.sort(key=lambda x: x[0])
#    print(A)
    dp = [float("inf")]*N
    dp[0] = 0
    for (s, t, c) in A:
        for j in range(s, t+1):
            dp[j-1] = min(dp[j-1], dp[s-1] + c)
    ans = dp[N-1]
#    print(dp)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
lrc = []
for _ in range(m):
    l, r, c = map(int, input().split())
    lrc.append((l, r, c))
lrc.sort()

inf = 10**18
dp = [inf]*(n+1)
dp[1] = 0

for l, r, c in lrc:
    for i in range(r, l, -1):
        if dp[i] > dp[l] + c:
            dp[i] = dp[l] + c
        else:
            break

ans = -1 if dp[n] == inf else dp[n]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
LRC = []
for _ in range(M):
    LRC.append(list(map(int,input().split())))
LRC.sort(key=lambda x: x[1])
LRC.sort(key=lambda x: x[0])

dp=[float('inf') for _ in range(N+10)]
dp[0] = 0
dp[1] = 0

for l,r,c in LRC:
    for d in range(1,r-l+1):
        dp[l+d] = min(dp[l]+c,dp[l+d])
if dp[N] == float('inf'):
    print('-1')
else:
    print(int(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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:
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    A.sort(key=lambda x: x[0])
#    print(A)
    dp = [[float("inf")]*N for _ in range(M+1)]
    dp[0][0] = 0
    for i, (s, t, c) in enumerate(A):
        for j in range(N+1):
            if j-1 < s or j-1 >= t:
                dp[i+1][j-1] = dp[i][j-1]
                if j-1 >= t and dp[i+1][j-1] == float("inf"):
                    break
            else:
                dp[i+1][j-1] = min(dp[i][j-1], dp[i][s-1] + c)
    ans = dp[M][N-1]
#    for x in dp:
#        print(x)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import floyd_warshall

N, M = map(int, input().split())
NN = [[0] * N for _ in range(N)]
for i in range(M):
    l, r, c = map(int, input().split())
    for j in range(l,r):
        for k in range(l+1,r+1):
            if NN[j-1][k-1] >= c or NN[j-1][k-1] == 0:
                NN[j-1][k-1] = c
                NN[k-1][j-1] = c
  
d = floyd_warshall(NN, directed = False)

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

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
import numpy as np

query = list()
for i in range(M):
  query.append(tuple(map(int,input().split())))
  
query.sort()
dp = np.zeros(N)
dp[1:] = np.inf
for l,r,c in query:
  dp[l-1:r] = np.minimum(dp[l-1]+c, dp[l-1:r])

print(int(dp[-1]) if dp[-1] != np.inf else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
input = sys.stdin.readline
inf = 10**10

class Dijkstra:

    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば，始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(adj)          # グラフのノード数
        dist = [inf for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [inf for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != inf and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_path(goal, prev), dist[goal]
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != inf:
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))


N, M = map(int, input().split())
adj = [[inf] * (N + 1) for _ in range(N + 1)]
for i in range(2, N + 1):
    adj[i][i - 1] = 0
for _ in range(M):
    l, r, c = map(int, input().split())
    adj[l][r] = c

graph = Dijkstra()
lst, d = graph.dijkstra(adj, 1, N)

if d == 10 ** 10:
    print(-1)
else:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
import numpy as np

query = list()
for i in range(M):
  query.append(tuple(map(int,input().split())))
  
query.sort()
dp = np.zeros(N)
dp[1:] = np.inf
for l,r,c in query:
  dp[l-1:r] = np.minimum(np.ones(r-l+1)*(dp[l-1]+c), dp[l-1:r])

print(int(dp[-1]) if dp[-1] != np.inf else -1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

N,M = map(int, sys.stdin.readline().rstrip().split(" "))
pathes = collections.defaultdict(list)
for _ in range(M):
    L, R, C = map(int, sys.stdin.readline().rstrip().split(" "))
    pathes[L].append((R, C))

currents = {}
if not 1 in pathes:
    print(-1)
    exit(0)
current_minimum = 0
for n in range(1, N, 1):
    if n in pathes:
        for R, C in pathes[n]:
            if R in currents:
                currents[R] = min(currents[R], C+current_minimum)
            else:
                currents[R] = C+current_minimum
    if n == 1:
        current_minimum = min(currents.values())
    if n in currents:
        del currents[n]
        if len(currents) == 0:
            print(-1)
            exit(0)
        current_minimum = min(currents.values())
    # print(n, current_minimum, currents)


print(current_minimum)
exit(0)

Submission status: Time Limit Exceeded

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

for i in range(1, n):
    for j in range(n):
        cost[0][j] = min(cost[0][j], cost[0][i]+cost[i][j])

ans = cost[0][n-1]
print(ans if ans!=1e10 else -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[0])
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:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, 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())
ro = [[float("inf") 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] > c:
                ro[j][k] = c
                ro[k][j] = c
cost = ro         
te = dijkstra(0,n,n-1,cost)
if te[-1] == float("inf"):
    print(-1)
else:
    print(te[-1])

Submission status: Time Limit Exceeded

Solution code:
#D
import math
import numpy as np
N, M = map(int, input().split())
route_list = [[0 for i in range(N)] for i in range(N)]
for i in range(M):
    L, R, C = map(int, input().split())
    for i in range(L, R):
        for j in range(i, R):
            if route_list[i-1][j] == 0:
                route_list[i-1][j] = C
            else:
                route_list[i-1][j] = min(route_list[i-1][j], C)

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

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

# @GDaigo さんのコメントより関数の追加 2017/03/18
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 = np.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] is np.inf:
    print("-1")
else:
    print(distance[node_num - 1])

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 = 1
dp[1] = 0
for l, r, c in LRC:
    if l > visited:
        print(-1)
        exit()
    if r > visited:
        visited = r
    x = dp[l] + c
    for i in range(l, r+1):
        dp[i] = min(dp[i], x)
if dp[N] == INF:
    print(-1)
else:
    print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, m = map(int, input().split())
lrc = []
for _ in range(m):
    l, r, c = map(int, input().split())
    lrc.append((r, l, c))
lrc.sort(reverse=True)

inf = 10**18
dp = np.ones(n+1, dtype=np.int32)*inf
dp[n] = 0

for r, l, c in lrc:

    for i in range(l, r):
        if dp[i] > dp[r] + c:
            dp[i] = dp[r] + c
        else:
            break

ans = -1 if dp[1] == inf else dp[1]
print(ans)

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

    dist = [float("inf") for i in range(num)]
    dist[0] = 0
    for i in range(num):
        du = dist[i]
        l = i
        for k, j in vedge[i]:
            if dist[j] <= du + k:
                continue
            for j in range(l + 1, j + 1):
                if dist[j] > du + k:
                    dist[j] = du + k
                    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:
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), reverse=True)
LRC.sort(key=itemgetter(0))

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M =map(int, input().split())
route_list  = [[float("inf") for i in range(N)] for i 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)
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, 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



ans = dijkstra(0,N,M,route_list)[-1]
if ans ==float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

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


def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    A.sort(key=lambda x: x[0])
#    print(A)
    dp = [[float("inf")]*N for _ in range(M+1)]
    dp[0][0] = 0
    for i, (s, t, c) in enumerate(A):
        for j in range(N+1):
            if j-1 < s or j-1 >= t:
                dp[i+1][j-1] = dp[i][j-1]
            else:
                dp[i+1][j-1] = min(dp[i][j-1], dp[i][s-1] + c)
    ans = dp[M][N-1]
#    for x in dp:
#        print(x)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
n,m=map(int,input().split())
INF = 10**15
dp = [INF]*(n-1)
dp.insert(0,0)

ls=[]

for i in range(m):
    l=list(map(int,input().split()))
    ls.append(l)

ls.sort()

for i in range(m):
    L=ls[i][0]
    R=ls[i][1]
    C=ls[i][2]
    for j in range(L,R):
        dp[j]=min(dp[j],dp[L-1]+C)
        
if dp[-1]==INF:
    ans=-1
else:
    ans=dp[-1]

print(ans)

Submission status: Time Limit Exceeded

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

i = 1
ip = 0
M = [None]*(N+1)
M[1] = 0
while i<N:
    while ip<len(P) and P[ip][0]<=i:
        p = P[ip]
        Q.append((p[0], p[1], p[2]+M[p[0]]))
        ip+=1

    Q.sort(key=lambda x:-x[1])
    j = len(Q)-1
    while j>=0 and Q[j][1]<=i: j-=1
    Q = Q[:j+1]

    if len(Q)==0:
        print(-1)
        exit()

    qmin = min(Q, key=lambda x:x[2])
    for r in range(i+1, qmin[1]+1):
        M[r] = qmin[2]

    i = qmin[1]

print(M[N])

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(s) for s in input().split()]
ls=[[int(s) for s in input().split()] for i in range(M)]
ls.sort()
#print(ls)
dp=[10**14]*(N+1)
dp[0]=0
dp[1]=0
for e in ls:
  for i in range(e[0]+1,e[1]+1):
    dp[i]=min([dp[i],dp[e[0]]+e[2]])
#  print(dp)
if dp[N]<10**14:
  print(dp[N])
else:
  print(-1)

Submission status: Time Limit Exceeded

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

INF = 10**20
N,M = map(int,input().split(' '))
g = defaultdict(set)
cost = defaultdict(lambda : INF)
lmin = [N+1] * (N+1)
LRC = []
for i in range(1,M+1):
    l,r,c = list(map(int,input().split(' ')))
    for j in range(l,r):
        g[j].add(r)
        cost[(j,r)] = min(cost[(j,r)],c)

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 in g[s]:
        c = cost[(s,t)]
        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:
n, m = map(int, raw_input().split())
edges = []
for _ in range(m):
    edges.append(map(int, raw_input().split()))
edges.sort()

dist = [float('inf')] * (n + 1)
dist[1] = 0
for l, r, c in edges:
    for e in xrange(l + 1, r + 1):
        dist[e] = min(dist[l] + c, dist[e])

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

Submission status: Time Limit Exceeded

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

graph = [[] for _ in range(N)]

for i, (Li, Ri, Ci) in enumerate(LRC):
    graph[Li - 1].append((Ri, Ci))

for i, (Li, Ri, Ci) in enumerate(LRC):
    for idx in range(Ri - Li):
        if len(graph[(Ri - idx - 1) - 1]) > 0:
            graph[Ri - 1].append(((Ri - idx - 1), 0))

# for i in range(N):
#     print("#", graph[i])
            
import heapq

inf = 10 ** 18
d = [inf] * N

q = [(0, 1)] # cost, pos
while len(q) > 0:
    cost, src = heapq.heappop(q)
    for dst, c_dst in graph[src - 1]:
        if cost + c_dst < d[dst - 1]:
            d[dst - 1] = cost + c_dst
            heapq.heappush(q, (cost + c_dst, dst))

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