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:
import sys
from heapq import heappush, heappop
input = sys.stdin.readline


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


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

    A = dijkstra(0, N, E)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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


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

    A = dijkstra(0, N, E)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


# ダイクストラ法. O(|E|log|V|)
# 頂点数 n, *負の辺が無い* グラフで、頂点 s から各頂点への最短距離を求める (存在しないときはinf)
# 隣接リスト edge[i]: 頂点 i から [cost, dst] のリスト (heapq のため cost が先)
# 辺 i,j w が与えられたとき edge[i], edge[j] とも必要な点に注意
def dijkstra(s, n, edge):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    for e in edge[s]:
        heapq.heappush(q, e)
    while q:
        minedge = heapq.heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue
        d[v] = minedge[0]
        for e in edge[v]:
            heapq.heappush(q, [e[0]+d[v], e[1]])
    return d


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

    A = dijkstra(0, N, E)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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

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

h = []
heapq.heappush(h, (0, n-1))
closed = 0
while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    closed |= (1 << n0)
    if n0 == 0:
        print(c0)
        exit()

    for n1, c1 in links[n0]:
        if (closed & (1 << n1)) != 0:
            continue
        heapq.heappush(h, (c0 + c1, n1))

    n2 = n0 + 1
    if n2 < n:
        if (closed & (1 << n2)) == 0:
            heapq.heappush(h, (c0, n0 + 1))

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([-1] * i)
    links.append([])

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

h = []
heapq.heappush(h, (0, n-1))
closed = 0
while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    closed |= (1 << n0)
    if n0 == 0:
        print(c0)
        exit()

    for n1, c1 in links[n0]:
        if (closed & (1 << n1)) != 0:
            continue
        heapq.heappush(h, (c0 + c1, n1))

    n2 = n0 + 1
    if n2 < n:
        if (closed & (1 << n2)) == 0:
            heapq.heappush(h, (c0, n0 + 1))

print("-1")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int,input().split())
side = [[[i-1,0]]for i in range(N)]
side[0] = []
for i in range(M):
    l,r,c = map(int,input().split())
    side[l-1].append([r-1,c])
node = [float('inf')]*N
node[0] = 0
queue = deque([0])
while queue:
    q = queue.popleft()
    for n, c in side[q]:
        if node[n] > node[q] + c:
            node[n] = node[q]+c
            queue.append(n)
if node[-1] == float('inf'):
    print(-1)
else:
    print(node[-1])

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline
input=sys.stdin.readline

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

def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

def main():
    
    d=[[]for i in range(n+1)]
    
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append((b,c))
        d[b].append((a,c))
    for i in range(1,n+1):
        d[i].append((i-1,0))
#    print(d)
    x=DIJKSTRA(1,d)[n]
    if x!=float("inf"):
        print(x)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
node_num = N
route_list = [[10**9 + 1] * N for _ in range(N)]
for i in range(M):
    L, R, C = map(int, input().split())
    route_list[L-1][R-1] = min(C, route_list[L-1][R-1])
for i in range(N-1):
    route_list[i+1][i] = 0
unsearched_nodes = list(range(node_num))
distance = [10**9] * 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 = 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:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline
input=sys.stdin.readline

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

def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

def main():
    
    d=[[]for i in range(n+1)]
    
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append((b,c))
        d[b].append((a,c))
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            d[j].append((i,0))
#    print(d)
    x=DIJKSTRA(1,d)[n]
    if x!=float("inf"):
        print(x)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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

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

h = []
heapq.heappush(h, (0, n-1))
closed = 0
while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    closed |= (1 << n0)
    if n0 == 0:
        print(c0)
        exit()

    for n1, c1 in links[n0]:
        if (closed & (1 << n1)) != 0:
            continue
        heapq.heappush(h, (c0 + c1, n1))

    for n1 in range(n0 + 1, n):
        if (closed & (1 << n1)) != 0:
            break
        heapq.heappush(h, (c0, n1))

print("-1")

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline
input=sys.stdin.readline

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

def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

def main():
    
    d=[[]for i in range(n+1)]
    
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append((b,c))
        d[b].append((a,c))
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            d[j].append((i,0))
#    print(d)
    x=DIJKSTRA(1,d)[n]
    if x!=float("inf"):
        print(x)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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



def dijkstra(N, adj, start, goal):
    '''
    ダイクストラアルゴリズムによる最短経路を求めるメソッド
    入力
    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 = N + 1          # グラフのノード数
    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 q:
        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                      # 前の頂点を記録
                
    return dist[goal]
        



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

d = dijkstra(N, adj, 1, N)

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

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 = [int(x) for x in input().split()]

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

Submission status: Time Limit Exceeded

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

INF = 10**20
N,M = map(int,input().split(' '))
g = defaultdict(list)
for i in range(2,N+1):
    g[i].append((i-1,0))
for i in range(1,M+1):
    input = sys.stdin.readline
    l,r,c = list(map(int,input().split(' ')))
    g[l].append((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,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 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], np.minimum.accumulate(dp[L:R + 1] + C)[1:])

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

Submission status: Time Limit Exceeded

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



def dijkstra(N, adj, start, goal):
    '''
    ダイクストラアルゴリズムによる最短経路を求めるメソッド
    入力
    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 = N + 1          # グラフのノード数
    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                      # 前の頂点を記録
                
    return dist[goal]
        



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

d = dijkstra(N, adj, 1, N)

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

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(list)
for i in range(2,N+1):
    g[i].append((i-1,0))
for i in range(1,M+1):
    l,r,c = list(map(int,input().split(' ')))
    g[l].append((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,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())
segment = [(1, 1, 0), (n, n, 0)]
node = {(1, 1, 0): [], (n, n, 0): []}
for _ in range(m):
    l, r, c = map(int, input().split())
    node[(l, r, c)] = []
    for s, e, tar_c in segment:
        if s <= l <= e or s <= r <= e:
            if e < r:
                node[(s, e, tar_c)].append((l, r, c))
            elif r < e:
                node[(l, r, c)].append((s, e, tar_c))
    segment.append((l, r, c))
#print(node)

def bfs(l, r, c, ans):
    n_nodes = node[(l, r, c)]
    if r==n:
        return ans+c
    if n_nodes == []:
        return float("inf")
    else:
        return min([bfs(s, e, n_c, ans + c) for s, e, n_c in n_nodes])


ans = bfs(1, 1, 0, 0)
if math.isinf(ans):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

INF = float('inf')
def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    dist = {v: INF for v in V}
    heap = []
    dist[s] = 0; rem = len(V);
    heappush(heap, (0, s))
    while heap and rem:
        d, v = heappop(heap)
        # don't need to check when the stored value is greater than provisional distance
        if d > dist[v]: continue
        rem -= 1;
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                dist[u] = temp
                heappush(heap, (temp, u))
    return dist

N, M = map(int, input().split())
V = list(range(N))
E = defaultdict(dict)
for _ in range(M):
    l, r, c = map(int, input().split())
    l, r = l-1, r-1
    E[l][r] = min(c, E[l].setdefault(r, INF))
    for i in range(l, r+1):
        E[i+1][i] = 0
dist = dijkstra(V, E, 0)
print(dist[N-1] if dist[N-1] != INF else -1)

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()
    INF = 10 ** 18
    dp = [INF for i in range(n)]
    dp[0] = 0
    for l, r, c in a:
        tp = dp[l - 1] + c
        for i in range(r - 1, l - 1, -1):
            if dp[i] == INF:
                dp[i] = min(dp[i], tp)
            elif tp < dp[i]:
                dp[i] = tp
            else:
                break
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.ones(n, dtype=np.int) * (c.sum() + 1)
dp[0] = 0
flag = True
for i in range(1, n):
  use = (l < i) * (r >= i)
  if np.all(~use):
    flag = False
    break
  dp[i] = np.min(dp[l[use]] + c[use])
  
if flag:
  print(dp[-1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
#D
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:
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 = False
    if not chk:
        break
if P[-1] == CM:
    print(-1)
else:
    print(P[-1])

Submission status: Time Limit Exceeded

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

event.sort(key=itemgetter(0))
paths = {}
now_dist = 0
for ev in event:
    x = ev[0]
    for s in paths:
        if(dists[x]<paths[s][1]):
            paths[s][1] = dists[x]
        dists[x] = min(dists[x], paths[s][0]+paths[s][1])

    if(ev[2]==1):
        paths[ev[3]] = [ev[1], dists[ev[0]]]
    else:
        del paths[ev[3]]

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

Submission status: Time Limit Exceeded

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


class SegmentTree():
    def __init__(self, values, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        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] = min(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] = min(
                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 min(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
        if h < l:
            h = l-1
        for i in range(h,r):
            V[i] = min(V[i], V[h]+c)

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

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

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:
n, m = map(int, input().split())
lrc = []
for _ in range(m):
    lrc.append(tuple(map(int, input().split())))
lrc.sort()

inf = 10**15
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)