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:
#D
import math
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) #ノードの数
inf = 10 ** 10
unsearched_nodes = list(range(node_num)) # 未探索ノード
distance = [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):
    inf = 10 ** 10
    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 = 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 inf:
    print("-1")
else:
    print(distance[node_num - 1])

Submission status: Time Limit Exceeded

Solution code:
#import sys
#import re
import heapq

input = raw_input
range = xrange
def initialize_graph():
    graph = {}
    n, edge_list = read_file()
    for edge_inf in edge_list:
        node1 = edge_inf[0]
        node2 = edge_inf[1]
        cost = edge_inf[2]
        graph = set_new_node(graph, node1, node2)
        graph[node1][node2] = cost
        graph[node2][node1] = cost
    return n, graph

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

def solve_by_dijkstra(graph, n):
    min_dist_dict = {}
    prev_node_dict = {}
    q = []
    heapq.heappush(q, (0, 1))
    
    prev_node = ''

    while True:
        if q == []:
            return None, None
        dist, node = heapq.heappop(q)
        min_dist_dict[node] = dist
        prev_node_dict[node] = prev_node
        if node == n: 
            return min_dist_dict, prev_node_dict
        prev_node = node
        culc_min_dist_and_put(graph, q, node, min_dist_dict, prev_node_dict)
    return None, None

def culc_min_dist_and_put(graph, q, departure_node, min_dist_dict, prev_node_dict):
    for arrival_node in graph[departure_node].keys():
        tmp_d = min_dist_dict[departure_node] + graph[departure_node][arrival_node]
        if arrival_node in min_dist_dict.keys():
            if tmp_d < min_dist_dict[arrival_node]:
                min_dist_dict[arrival_node] = tmp_d
                heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))
        else:
            min_dist_dict[arrival_node] = tmp_d
            heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))

def main():
    n, graph = initialize_graph()
    min_dist_dict, prev_node_dict = solve_by_dijkstra(graph, n)
    if min_dist_dict is not None:
        out = min_dist_dict[n]
    else:
        out = -1
    print(out)

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

    #edge_list = []
    #pairs = []
    inputs = sorted([list(map(int, input().split(" "))) for _ in range(m)], key=lambda x: x[2], reverse=True)

    edge_dict = {}
    for l, r, w in inputs:
        #print("i", _, l, r, w)
        for s in range(l, r+1):
            for t in range(s+1, r+1):
                pair = (s, t)
                #if pair in pairs:
                #    continue
                #ws[s][t] = min(ws[s][t], w)
                #pairs.append(pair)
                edge_dict[(s, t)] = [s, t, w]

    edge_list = list(edge_dict.values())
    #edge_list.append([s, t, w])


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


main()

Submission status: Time Limit Exceeded

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


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush
import numpy as np

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

    while heap:
        l, r, c = heappop(heap)
        s = dp[l]
        d = np.where(dp[l+1:r+1] < s+c, dp[l+1:r+1], s+c)
        dp[l+1:r+1] = d
            
    if dp[N-1] == INF:
        return -1
    
    return dp[N-1]

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

Submission status: Time Limit Exceeded

Solution code:
#D
import math
N, M = map(int, input().split())
inf = 10 ** 10
route_list = [[inf 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):
            route_list[i-1][j] = min(route_list[i-1][j], C)

def dijkstra(s,n,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

d_ret = dijkstra(0, N, route_list)
res = d_ret[-1]
if res == inf:
    print("-1")
else:
    print(res)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

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

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

    cand = float("inf")
    while q:
        y, z = heappop(q)
        if y >= l:
            heappush(q, (y, z))
            break

    for y, z in q:
        if y < r:
            cand = min(cand, z)
        else:
            heappush(q, (y, z))
            break

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

# print(q)

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

print(ans)

Submission status: Time Limit Exceeded

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


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

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

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

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


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def solve():
    N, M = map(int,input().split())
    E = [tuple(map(int,input().split())) for _ in range(M)]
    V = [float('inf') for _ in range(N)]
    V[0]=0
    E.sort()
    h = 0
    for e in E:
        l,r,c = e
        for i in range(max(h,l-1),r):
            V[i] = min(V[i], min(V[l-1:r])+c)

    return str(V[-1]) if V[-1] != float('inf') else '-1'

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
a.sort()
dp = [10 ** 18 for i in range(n)]
dp[0] = 0
for l, r, c in a:
    for i in range(l - 1, r):
        dp[i] = min(dp[i], dp[l - 1] + c)
if dp[-1] == 10 ** 18:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#import sys
#import re
import heapq

input = raw_input
range = xrange
def initialize_graph():
    graph = {}
    n, edge_list = read_file()
    for edge_inf in edge_list:
        node1 = edge_inf[0]
        node2 = edge_inf[1]
        cost = edge_inf[2]
        graph = set_new_node(graph, node1, node2)
        graph[node1][node2] = cost
        graph[node2][node1] = cost
    return n, graph

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

def solve_by_dijkstra(graph, n):
    min_dist_dict = {}
    prev_node_dict = {}
    q = []
    heapq.heappush(q, (0, 1))
    
    prev_node = ''

    while True:
        if q == []:
            return None, None
        dist, node = heapq.heappop(q)
        min_dist_dict[node] = dist
        prev_node_dict[node] = prev_node
        if node == n: 
            return min_dist_dict, prev_node_dict
        prev_node = node
        culc_min_dist_and_put(graph, q, node, min_dist_dict, prev_node_dict)
    return None, None

def culc_min_dist_and_put(graph, q, departure_node, min_dist_dict, prev_node_dict):
    for arrival_node in graph[departure_node].keys():
        tmp_d = min_dist_dict[departure_node] + graph[departure_node][arrival_node]
        if arrival_node in min_dist_dict.keys():
            if tmp_d < min_dist_dict[arrival_node]:
                min_dist_dict[arrival_node] = tmp_d
                heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))
        else:
            min_dist_dict[arrival_node] = tmp_d
            heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))

def main():
    n, graph = initialize_graph()
    min_dist_dict, prev_node_dict = solve_by_dijkstra(graph, n)
    if min_dist_dict is not None:
        out = min_dist_dict[n]
    else:
        out = -1
    print(out)

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

    edge_list = []
    pairs = []
    inputs = sorted([list(map(int, input().split(" "))) for _ in range(m)], key=lambda x: x[2])
    for l, r, w in inputs:
        #print("i", _, l, r, w)
        for s in range(l, r+1):
            for t in range(s+1, r+1):
                pair = (s, t)
                if pair in pairs:
                    continue
                #ws[s][t] = min(ws[s][t], w)
                pairs.append(pair)
                edge_list.append([s, t, w])


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


main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
route_list = [[float("inf")]*n for _ in range(n)]
lrc = [ list(map(int, input().split())) for _ in range(m) ]
for l, r, c in lrc:
  for i in range(l, r):
    for j in range(i+1, r+1):
      route_list[i-1][j-1] = min(route_list[i-1][j-1], c)
      route_list[j-1][i-1] = min(route_list[j-1][i-1], c)
  
  
node_num = n

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

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

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

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


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, M = map(int, input().split())
LRCs = []
for i in range(M):
  L, R, C = map(int, input().split())
  L, R = L-1, R-1
  LRCs.append((L, R, C))
LRCs.sort()
#print(LRCs)
Ds = [-1]*N
Ds[0] = 0
Rs = sorted([0]+[R for L, R, C in LRCs])
#print(Rs)
for L, R, C in LRCs:
  i = bisect.bisect_left(Rs, L)
  j = bisect.bisect_left(Rs, R)
  #print(i, j)
  if i == len(Rs):
    continue
  L = Rs[i]
  #print(L, Ds)
  if Ds[L] < 0:
    continue
  for k in range(i+1, j+1):
    R = Rs[k]
    if Ds[R] < 0:
      Ds[R] = Ds[L]+C
    else:
      Ds[R] = min(Ds[R], Ds[L]+C)
r = Ds[-1]
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

N,M = map(int,input().split(' '))
K = [None]*M
for i in range(M):
    K[i] = list(map(int,input().split(' ')))

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

for i in range(M):
    l,r,c = K[i]
    for j in range(l-1,r):
        for k in range(j+1,r):
            m = MAP[j][k]
            if m==None:
                MAP[j][k] = c
            else:
                if c<m:
                    MAP[j][k] = c

shortest = [None]*N
shortest[0] = 0

#今何番目nodeか,N,nodeが持ってる辺,MAP
def bfs(i,N,l,shortest):
    #そこまでの最短ルート
    cnt = shortest[i]
    if cnt==None:
        print(-1)
        exit()
    #当該のnodeからの距離
    for i in range(i,N):
        m = l[i]
        if m==None:
            continue
        new_one = shortest[i]
        if not new_one==None:
            #m+cntは1からの距離
            shortest[i] = min(new_one,m+cnt)
        else:
            shortest[i] = m+cnt
    return shortest

for i in range(N):
    l = MAP[i]
    shortest = bfs(i,N,l,shortest)
if shortest[-1]==None:
    print(-1)
else:
    print(shortest[-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq
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)]

def dijkstra_heap(s,edge):
    d = [float("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



edge = [[] for i in range(n)]

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

    for x in range(l, r):
        for y in range(x+1, r+1):

            edge[x].append([z,y])
            edge[y].append([z,x])

l = dijkstra_heap(0, edge)
res = l[-1]

if res == float('inf'):
    print(-1)
else:
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = map(int, input().split())
INF = 10**9
g = [[INF for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    L, R, C = map(int, input().split())
    for i in range(L, R+1):
        for j in range(L, R+1):
            if i == j:
                g[i][j] = 0
            else:
                g[i][j] = min(g[i][j], C)

def dijkstra(adj, s):
    num = len(adj)
    dist = [INF for _ in range(num)]
    prev = [INF for _ in range(num)]
    dist[s] = 0
    q = []
    heapq.heappush(q, (0, s))
    while len(q) != 0:
        prov_cost, src = heapq.heappop(q)
        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
                heapq.heappush(q, (dist[dest], dest))
                prev[dest] = src
    return dist

ans = dijkstra(g, 1)[-1]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#D
import math
import numpy as np
N, M = map(int, input().split())
inf = 10 ** 10
route_list = [[inf 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):
            route_list[i-1][j] = min(route_list[i-1][j], C)

def dijkstra(s,n,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

d_ret = dijkstra(0, N, route_list)
res = d_ret[-1]
if res == inf:
    print("-1")
else:
    print(res)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#import re
import heapq

input = raw_input
range = xrange
def initialize_graph():
    graph = {}
    n, edge_list = read_file()
    for edge_inf in edge_list:
        node1 = edge_inf[0]
        node2 = edge_inf[1]
        cost = edge_inf[2]
        graph = set_new_node(graph, node1, node2)
        graph[node1][node2] = cost
        graph[node2][node1] = cost
    return n, graph

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

def solve_by_dijkstra(graph, n):
    min_dist_dict = {}
    prev_node_dict = {}
    q = []
    heapq.heappush(q, (0, 1))
    
    prev_node = ''

    while True:
        if q == []:
            return None, None
        dist, node = heapq.heappop(q)
        min_dist_dict[node] = dist
        prev_node_dict[node] = prev_node
        if node == n: 
            return min_dist_dict, prev_node_dict
        prev_node = node
        culc_min_dist_and_put(graph, q, node, min_dist_dict, prev_node_dict)
    return None, None

def culc_min_dist_and_put(graph, q, departure_node, min_dist_dict, prev_node_dict):
    for arrival_node in graph[departure_node].keys():
        tmp_d = min_dist_dict[departure_node] + graph[departure_node][arrival_node]
        if arrival_node in min_dist_dict.keys():
            if tmp_d < min_dist_dict[arrival_node]:
                min_dist_dict[arrival_node] = tmp_d
                heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))
        else:
            min_dist_dict[arrival_node] = tmp_d
            heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))

def main():
    n, graph = initialize_graph()
    min_dist_dict, prev_node_dict = solve_by_dijkstra(graph, n)
    if min_dist_dict is not None:
        out = min_dist_dict[n]
    else:
        out = -1
    print(out)

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

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

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

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


main()

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 dist[goal]
            # return self.get_path(goal, prev)
        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()
d = graph.dijkstra(adj, 1, N)

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

Submission status: Time Limit Exceeded

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

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

lrc.sort(key = lambda x:x[0])

dis = [-1] * n
dis[0] = 0

for i in range(m):
    if dis[lrc[i][0]-1] != -1:
        for j in range(lrc[i][0],lrc[i][1]):
            if dis[j] == -1:
                dis[j] = dis[lrc[i][0]-1] + lrc[i][2]
            else:
                dis[j] = min(dis[lrc[i][0]-1] + lrc[i][2], dis[j])

print(dis[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def dijkstra(s,n,m,cost):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    d[1] = cost[0][1]
    for i in range(2, n):
        for j in range(0,i):
            if d[i] > d[j] + cost[j][i]:
                d[i] = d[j] + cost[j][i]
    return d[n - 1]

################################
n, m = map(int, input().split())
cost = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(0, m):
    L, R, c = map(int, input().split())
    for j in range(L, R):
        for k in range(j, R):
            if cost[j - 1][k] > c:
                cost[j - 1][k] = c
result = dijkstra(0,n,m,cost)
if result == float("inf"):
    print(-1)
else:
    print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
import numpy as np
read = sys.stdin.read

N, M, *LRC = map(int, read().split())
dp = np.full(N + 1, np.inf)
dp[1] = 0

for L, R, C in sorted(list(zip(*[iter(LRC)] * 3)), key=itemgetter(0, 1)):
    dp[L + 1:R + 1] = np.minimum(dp[L + 1:R + 1], dp[L] + C)
    dp[L + 1:R + 1] = np.minimum(dp[L + 1:R + 1], np.minimum.accumulate(dp[L + 1:R + 1] + C))

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