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 heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    rmky = [set() for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = (l-1, r-1)
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
        if r < n:
            rmky[r].add(ky)
    for i in range(1, n):
        dics[i].update(dics[i-1])
        for v in rmky[i]:
            dics[i].pop(v)
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if v > dist[p]:
            continue
        if p == n-1:
            break
        for l, r in dics[p].keys():
            for i in range(l, r+1):
                if i == p:
                    continue
                dics[i].pop((l, r))
                if dist[i] > v + dics[p][(l, r)]:
                    dist[i] = v + dics[p][(l, r)]
                    heapq.heappush(hq, [dist[i], i])
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    rmky = [set() for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = (l-1, r-1)
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
        if r < n:
            rmky[r].add(ky)
    for i in range(1, n):
        dics[i].update(dics[i-1])
        for v in rmky[i]:
            dics[i].pop(v)
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    st = set()
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if v > dist[p]:
            continue
        if p == n-1:
            break
        for l, r in dics[p].keys():
            if (l, r) in st:
                continue
            for i in range(l, r+1):
                if dist[i] > v + dics[p][(l, r)]:
                    dist[i] = v + dics[p][(l, r)]
                    heapq.heappush(hq, [dist[i], i])
            st.add((l, r))
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

edge=[[] for _ in range(N)]
edges=[]
s=set([N-1])
for _ in range(M):
    l,r,c=map(int,input().split())
    l-=1
    edges.append((l,r,c))
    s.add(l)
V=list(s)
V.sort()
for l,r,c in edges:
    left=bisect_right(V,l)
    right=bisect_left(V,r)
    for i in V[left:right]:
        edge[l].append((c,i))
from heapq import heappop,heappush
# edges=[[(cost1,v1),(cost2,v2)],...]
def dijkstra(start,n,edges):
    d=[INF]*n
    used=[False]*n
    d[start]=0
    used[start]=True
    edgelist=[]
    for edge in edges[start]:
        heappush(edgelist,edge)
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        d[v]=minedge[0]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,(edge[0]+d[v],edge[1]))
    return d

d=dijkstra(0,N,edge)
print(d[-1] if d[-1]!=INF else -1)

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    N,M=MI()
    
    #############
    INF = 10**16

    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [INF]*(2*N0)
    lazy = [None]*(2*N0)

    # 伝搬対象の区間を求める
    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1

    # 遅延伝搬処理
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v is None:
                continue
            lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
            lazy[i-1] = None

    # 区間[l, r)をxで更新
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)

        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = data[R-1] = x
            if L & 1:
                lazy[L-1] = data[L-1] = x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            data[i-1] = min(data[2*i-1], data[2*i])

    # 区間[l, r)内の最小値を求める
    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r

        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])
            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
    #############
    
    L=[0]*M
    R=[0]*M
    C=[0]*M
    for i in range(M):
        l,r,c=MI()
        l-=1
        r-=1
        L[i]=l
        R[i]=r
        C[i]=c
        
    R,C,L=zip(*sorted(zip(R,C,L)))
        
    
    
    #rが小さいものから見て(rが同じならcが小さい)確定させていく
    now=0#確定させたとこと
    update(0,1,0)
    
    for i in range(M):
        r=R[i]
        l=L[i]
        c=C[i]
        m=query(l,now+1)#移動もとの範囲での最小値
        update(now+1,r+1,m+c)
        now=r
        
        #このままだと入力例3みたいに，コストは低いけどl,rがちかいみたいなのを先に処理してしまう
        #とりあえず右端だけ更新しとけばokか?
        
        if m+c<query(now,now+1):
            update(now,now+1,m+c)
        
        #print((l+1,r+1,c),now+1,m,m+c)
        
    ans=query(N-1,N)
    if ans>=INF:
        print(-1)
    else:
        print(ans)
    
        
    
        
        
    

main()

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    RCL=[[0,0,0]for _ in range(M)]
    
    #############
    INF = 10**16

    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [INF]*(2*N0)
    lazy = [None]*(2*N0)

    # 伝搬対象の区間を求める
    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1

    # 遅延伝搬処理
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v is None:
                continue
            lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
            lazy[i-1] = None

    # 区間[l, r)をxで更新
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)

        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = data[R-1] = x
            if L & 1:
                lazy[L-1] = data[L-1] = x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            data[i-1] = min(data[2*i-1], data[2*i])

    # 区間[l, r)内の最小値を求める
    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r

        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])
            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
    #############
    
    
    for i in range(M):
        l,r,c=MI()
        l-=1
        r-=1
        RCL[i]=[r,c,l]
        
    RCL.sort()
    
    #rが小さいものから見て(rが同じならcが小さい)確定させていく
    now=0#確定させたとこと
    update(0,1,0)
    
    for i in range(M):
        [r,c,l]=RCL[i]
        m=query(l,now+1)#移動もとの範囲での最小値
        update(now+1,r+1,m+c)
        now=r
        
        #このままだと入力例3みたいに，コストは低いけどl,rがちかいみたいなのを先に処理してしまう
        #とりあえず右端だけ更新しとけばokか?
        
        if m+c<query(now,now+1):
            update(now,now+1,m+c)
        
        #print((l+1,r+1,c),now+1,m,m+c)
        
    ans=query(N-1,N)
    if ans>=INF:
        print(-1)
    else:
        print(ans)
    
        
    
        
        
    

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

INF = 10 ** 15

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

LRCs = [tuple(map(int, input().split())) for _ in range(M)]
LRCs.sort(key = lambda t: (t[1], t[0]))

dp = np.full(N, INF, np.int64)
dp[0] = 0
for L, R, C in LRCs:
    while dp[R-1] > dp[L-1] + C:
        dp[R-1] = dp[L-1] + C
        R -= 1

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
inf = 10 ** 15
dp = [inf for _ in range(n)]
edges = []
for _ in range(m):
    l, r, c = map(int, input().split())
    edges.append((l-1, r-1, c))

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

dp[0] = 0
for l, r, c in edges:
    for i in range(l+1, r+1):
        dp[i] = min(dp[i], dp[l] + c)

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

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

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

G = nx.DiGraph()
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    l, r, c = map(int, input().split())
    G.add_edge(l, r, weight=c)
    for x in range(l, r):
        G.add_edge(x + 1, x, weight=0)

try:
    print(nx.dijkstra_path_length(G, 1, N))
except nx.NetworkXNoPath:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
LRC.sort()


stack=[[0,-1,0]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
visited[1]=0
while stack:
    #print(stack)
    m,a,p=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(bisect_left(LRC,[p,0,0]),M):
            l,r,c=LRC[i]
            if l<=a:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r,a+1])
            else:
                break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
LRC.sort()


stack=[[0,-1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
visited[1]=0
while stack:
    #print(stack)
    m,a=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(M):
            l,r,c=LRC[i]
            if l<=a:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r])
            else:
                break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
RLC=[[r,l,c] for l,r,c in LRC]
RLC.sort()
stack=[[0,1,0]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a,p=heappop(stack)
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(p,M):
            r,l,c=RLC[i]
            if l<=a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,r,i+1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
LRC.sort()
stack=[[0,1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for l,r,c in LRC:
            if l>a:
                break
            elif a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,r])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
s=1
pres=0
while s!=pres:
    pres=s
    for l,r,c in LRC:
        if l<=s<r:
            s=max(s,r)
    if s==N:
        break
else:
    print(-1)
    exit()
stack=[[0,-1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for l,r,c in LRC:
            if l<=a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
stack=[[0,-1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for l,r,c in LRC:
            if l<=a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
stack=[[0,-1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for l,r,c in LRC:
            if l<=a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
RLC=sorted([[r,l,c] for l,r,c in LRC])
stack=[[0,1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(bisect_left(RLC,[a,0,0]),M):
            r,l,c=RLC[i]
            if l<=a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,r])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
stack=[[0,1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for l,r,c in LRC:
            if l<=a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,r])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
LRC=sorted([list(map(int,input().split())) for i in range(M)],key=lambda x:x[0])
class rmq:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[self.INF]*(2*self.N0)
        self.lazy=[None]*(2*self.N0)
    def gindex(self,l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1
    def propagates(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v
            self.lazy[i-1] = None
    def update(self,l, r, x):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            self.data[i-1] = min(self.data[2*i-1], self.data[2*i])
    def rmin(self,l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
d=rmq(N)
d.update(0,1,0)
for l,r,c in LRC:
    d.update(r-1,r,min(d.rmin(r-1,r),d.rmin(l-1,r-1)+c))
a=d.rmin(N-1,N)
print(a if a<d.INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

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

g = [[10**10 for _ in range(n)] for __ in range(n)]

for _ in range(m):
    l, r, c = map(int, input().split())
    g[l-1][r-1] = min(g[l-1][r-1], c)

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


d = [10**18] * n
d[0] = 0
q = [(0, 0)]
while q:
    dist_u, u = heappop(q)
    if d[u] < dist_u:
        continue
    for v, c in enumerate(g[u]):
        if d[v] > dist_u + c:
            d[v] = dist_u + c
            heappush(q, (d[v], v))


print(d[n-1] if d[n-1] != 10**10 else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

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

g = [[10**10 for _ in range(n)] for __ in range(n)]

for _ in range(m):
    l, r, c = map(int, input().split())
    g[l-1][r-1] = min(g[l-1][r-1], c)

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


d = [10**13] * n
d[0] = 0
q = [(0, 0)]
while q:
    dist_u, u = heappop(q)
    if d[u] < dist_u:
        continue
    for v, c in enumerate(g[u]):
        if d[v] > dist_u + c:
            d[v] = dist_u + c
            heappush(q, (d[v], v))


print(d[n-1] if d[n-1] != 10**10 else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

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

g = [[10**10 for _ in range(n)] for __ in range(n)]

for _ in range(m):
    l, r, c = map(int, input().split())
    g[l-1][r-1] = min(g[l-1][r-1], c)

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


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [10**13] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


d = dijkstra(0, n, g)
print(d[n-1] if d[n-1] != 10**10 else -1)

Submission status: Time Limit Exceeded

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

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

g = [[10**10 for _ in range(n)] for __ in range(n)]

flag = [0]*n  # flag[i]:i←i+1 に0のパスがある(0<=i<=n-1)

for _ in range(m):
    l, r, c = map(int, input().split())
    g[l-1][r-1] = min(g[l-1][r-1], c)
    flag[l-1] += 1
    flag[r-1] += -1

for i in range(1, n):
    flag[i] += flag[i-1]
    if flag[i-1] != 0:
        g[i][i-1] = 0


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [10**13] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


d = dijkstra(0, n, g)
print(d[n-1] if d[n-1] != 10**10 else -1)

Submission status: Time Limit Exceeded

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

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

g = [[10**10 for _ in range(n)] for __ in range(n)]

for _ in range(m):
    l, r, c = map(int, input().split())
    g[l-1][r-1] = min(g[l-1][r-1], c)
    for i in range(l, r):
        g[i][i-1] = 0


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [10**13] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


d = dijkstra(0, n, g)
print(d[n-1] if d[n-1] != 10**10 else -1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
for i in range(1,n):
  graph[i+1].append((i,0))
import heapq as hq
dist = [10**18]*(n+1)
dist[1] = 0
q = [(0,1)]
hq.heapify(q)
while q:
  d,x = hq.heappop(q)
  for y,dd in graph[x]:
    if dist[y] >= dist[x]+dd:
      dist[y] = dist[x]+dd
      hq.heappush(q,(dist[y],y))
if dist[n] == 10**18:
  print(-1)
else:
  print(dist[n])

Submission status: Time Limit Exceeded

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

E.sort()
inf = 10**15
seg = [inf]*(2*N-1)

def update(k, x):
    k += N-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = min(seg[2*k+1], seg[2*k+2])
        
def query(p, q):
    p += N-1
    q += N-2
    res = inf
    while q-p > 1:
        if p&1 == 0:
            res = min(res, seg[p])
        if q&1 == 1:
            res = min(res, seg[q])
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res = min(res, seg[q])
    else:
        res = min(res, seg[p], seg[q])
    return res

update(0, 0)
for e in E:
    d = query(e[1]-1, N)
    l = query(e[0]-1, N)
    if l+e[2] < d:
        update(e[1]-1, l+e[2])

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

Submission status: Time Limit Exceeded

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

def main():
    N,M = map(int,input().split())
    INF = 10**10+1
    root = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N-1):
        root[i+1][i] = 0
    for _ in range(M):
        a,b,c = map(int,input().split())
        root[a-1][b-1] = c
        root[b-1][a-1] = c
    
    dist = [INF for _ in range(N)]
    que = [(0,0)]
    dist[0] = 0
    while que:
        dif,now = heapq.heappop(que)
        for f,fol in enumerate(root[now]):
            if (fol != INF and dist[f] > dist[now] + fol):
                dist[f] = dist[now] + fol
                heapq.heappush(que,(dist[f],f))
                
    if dist[-1] == INF:
        print(-1)
    else:
        print(dist[-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

def main():
    N,M = map(int,input().split())
    edge = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N-1):
        edge[i+1][i] = 0
    for _ in range(M):
        l,r,c = map(int,input().split())
        edge[l-1][r-1] = c

    G = csgraph_from_dense(edge,null_value = -1)
    if dijkstra(G,indices = 0)[-1] == float("inf"):
        print(-1)
    else:
        print(int(dijkstra(G,indices = 0)[-1]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np
from operator import itemgetter

def main():
    N,M = map(int,input().split())
    root = [list(map(int,input().split())) for _ in range(M)]
    
    root.sort(key=itemgetter(0))
    d = [10**18 for _ in range(N)]
    d[0] = 0
    d = np.array(d)
    for l,r,c in root:
        if d[l-1] == 10**18:
            print(-1)
            exit()
        else:
            d[l:r] = np.minimum(d[l:r],d[l-1]+c)
            
    print(d[-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
LRC = [lr() for _ in range(M)]
LRC.sort()
INF = 10 ** 15
dp = [INF] * (N+1) # 1-indexed
dp[1] = 0
A = set([1]) # 最小値の候補
for l, r, c in LRC:
    rmv = []
    for ri in A:
        if ri < l:
            rmv.append(ri)
        else:
            dp[r] = min(dp[r], dp[ri] + c)
    for x in rmv:
        A.remove(x)
    A.add(r)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
LRC = [lr() for _ in range(M)]
LRC.sort()
INF = 10 ** 15
dp = np.full(N+1, INF) # 1-indexed
dp[1] = 0
for l, r, c in LRC:
    m = dp[l:r+1].min()
    dp[r] = min(dp[r], m + c)

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[[[i-1,0]]for i in range(n+1)]
a[0]=[]
for i in range(m):
    l,r,c=map(int,input().split())
    a[l].append([r,c])
q=[float("INF")]*(n+1)
q[1]=0
c=[[1,0]]
while c:
    s,t=c.pop(0)
    for i,j in a[s]:
        if q[i]>t+j:
            q[i]=t+j
            c.append([i,t+j])
print(-1 if q[-1]==float("INF") else q[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m=map(int,input().split())
a=sorted([list(map(int,input().split()))for i in range(m)])
b=np.array([float("INF")]*(n+1))
b[1]=0
for l,r,c in a:
    b[l:r+1]=np.minimum([b[l]+c]*(r-l+1),b[l:r+1])
print(-1 if b[-1]==float("INF") else int(b[-1]))