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


class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        self.n = n
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
            i >>= 1

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        # (k, l, r)
        # k   : 現在調べている区間のtree内index
        # l, r: kが表す区間の左右端index [l, r)
        q = [(1, 0, self.n2)]

        while q:
            k, l, r = q.pop()

            if a <= l and r <= b:
                result = min(result, self.tree[k])
                continue

            m = (l + r) // 2
            k <<= 1
            if a < m and l < b:
                q.append((k, l, m))
            if a < r and l < m:
                q.append((k + 1, m, r))

        return result


INF = 10 ** 18
n, m = map(int, input().split())
segments = [tuple(map(int, line.split())) for line in sys.stdin]
segments.sort()
sgt = SegTreeMin(n, INF)
sgt.update(0, 0)
for l, r, c in segments:
    use_current = sgt.get_min(l - 1, r - 1) + c
    not_current = sgt.get_min(r - 1, r)

    if use_current < not_current:
        sgt.update(r - 1, use_current)

ans = sgt.get_min(n - 1, n)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
class Dijkstra:
    def __init__(self,n):
        self.n = n
        self.lengths = [dict() for _ in range(n)]
        self.inf = float('inf')
    def register(self,v1,v2,l,multiple=True):
        self.lengths[v1][v2] = l
        if multiple:
            self.lengths[v2][v1] = l
    def solve(self,s1):
        d = [self.inf for _ in range(self.n)]
        d[s1] = 0
        paths = [None for _ in range(self.n)]
        paths[s1] = []
        Q = queue.PriorityQueue()
        Q.put((d[s1],s1))
        while not Q.empty():
            d1,v1 = Q.get()
            for v2,l in self.lengths[v1].items():
                val = d1 + l
                if val < d[v2]:
                    d[v2] = val
                    Q.put((val,v2))
                    paths[v2] = paths[v1] + [v1]
        return d, paths

N,M = map(int,input().split())
LRC = []
for _ in range(M):
    LRC.append(list(map(int,input().split())))
D = Dijkstra(N)
for l,r,c in LRC:
    D.register(l-1,r-1,c,False)
for i in range(N-1):
    D.register(i+1,i,0,False)
ans = D.solve(0)[0][-1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

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 = inpl()
a = [inpl() for i in range(m)]
cost = [[float('inf')] * n for i in range(n)]
for i in range(n-1):
    cost[i+1][i] = 0
for i in a:
    cost[i[0]-1][i[1]-1] = i[2]
res = dijkstra(0,n,m+n-1,cost)
if res[n-1] == float('inf'):
    print(-1)
else:
    print(res[n-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M=map(int,input().split())
path=[[0 if i==j or i==max(j-1,0) else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

dist=[float("inf")]*N
dist[0]=0
q=[[dist[i],i] for i in range(N)]
heapq.heapify(q)

while q:
  d,ind=heapq.heappop(q)
  if d<=dist[ind]:
    for i in range(N):
      if dist[i]>d+path[ind][i]:
        dist[i]=d+path[ind][i]
        heapq.heappush(q,[dist[i],i])

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

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
path=[[0 if i==j or i==max(j-1,0) else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

seen=[]
dist=[float("inf")]*N
dist[0]=0
v=-1
while v!=N-1:
  v=-1
  for i in range(N):
    if i not in seen and v==-1:
      v=i
    if i not in seen and dist[i]<dist[v]:
      v=i
  seen.append(v)
  for i in range(N):
    dist[i]=min(dist[v]+path[v][i],dist[i])
    
if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
S = [0] * n

for i in range(m):
    for j in range(2):
        C[i][j] -= 1

for i in range(m):
    S[C[i][0]] += 1
    S[C[i][1]] -= 1

for i in range(1, n):
    S[i] += S[i-1]

for i in range(n-1):
    if S[i] > 0:
        C.append([i+1, i, 0])

M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]].append([C[i][1], C[i][2]])
    if C[i][2] > 0:
        M[C[i][1]].append([C[i][0], C[i][2]])

import heapq

D = [float("inf")] * n
P = [-1] * n
D[0] = 0
V = [0] * n
Q = []
for v in range(n):
    heapq.heappush(Q, [D[v], v])

le = len(Q)
while le > 0:
    q = heapq.heappop(Q)
    le -= 1
    u = q[1]
    du = q[0]
    V[u] = 1
    for i in range(len(M[u])):
        v = M[u][i][0]
        luv = M[u][i][1]
        if V[v] == 0:
            alt = du + luv
            if D[v] > alt:
                D[v] = alt
                P[v] = u
                heapq.heappush(Q, [alt, v])
                le += 1

ans = D[-1]
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import heapq

N, M = [int(x) for x in stdin.readline().rstrip().split()]
B = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]

graph = [[10 ** 15] * N for _ in range(N)]
for i in range(1, N):
    graph[i][i - 1] = 0
for m in B:
    graph[m[0] - 1][m[1] - 1] = m[2]

d = [(0, 0)]
distance = [10 ** 15] * N
distance[0] = 0
color = ['white'] * N
heapq.heapify(d)

while len(d) > 0:
    temp, u = heapq.heappop(d)
    color[u] = 'black'
    if distance[u] < temp:
        continue
    for v in range(N):
        if color[v] != 'black':
            if distance[u] + graph[u][v] < distance[v]:
                distance[v] = distance[u] + graph[u][v]
                color[v] = 'gray'
                heapq.heappush(d, (distance[v], v))

if distance[N - 1] == 10 ** 15:
    print(-1)
else:
    print(distance[N - 1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq

INF=10**15
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append([R,C])
    adj[R].append([L,C])
for i in range(N-1):
    adj[i+1].append([i,0])
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,[s,table[s]])
                
while heap:
    q=heapq.heappop(heap)
    a=q[0]
    if q[1]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,[p,table[p]])
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq

INF=10**14
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(s,table[s]))
                
while heap:
    q=heapq.heappop(heap)
    a=q[0]
    if q[1]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,(p,table[p]))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq

INF=10**15
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(s,table[s]))
                
while heap:
    q=heapq.heappop(heap)
    a=q[0]
    if q[1]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,(p,table[p]))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq

INF=10**12
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
used=np.array([])
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(table[s],s))
used=np.append(used,s)
                
while heap and not(g in used):
    q=heapq.heappop(heap)
    a=q[1]
    used=np.append(used,a)
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if not(p in used):
            table[p]=np.minimum(table[p],table[a]+co)
            heapq.heappush(heap,(table[p],p))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import numpy as np
import sys

class rode():
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return self.y < other.y
    def __gt__(self, other):
        return other > self
    def __le__(self, other):
        return not(other > self)
    def __ge__(self, other):
        return not(self > other)

n,m = map(int,input().split())
da = [[] for i in range(n)]
for i in range(1,n):
    da[i].append([i-1,0])
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
pq=[]
ju = np.zeros(n,dtype=bool)
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, rode(i[0],i[1]))
while(len(pq)):
    now = heapq.heappop(pq)
    if now.x == n-1:
        print(now.y)
        sys.exit()
    if ju[now.x]:
        continue
    ju[now.x] = True
    for i in da[now.x]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,rode(i[0],now.y+i[1]))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq

INF=10**12
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
used=np.array([])
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(table[s],s))
used=np.append(used,s)
                
while heap and not(g in used):
    q=heapq.heappop(heap)
    a=q[1]
    used=np.append(used,a)
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if not(p in used):
            table[p]=min(table[p],table[a]+co)
            heapq.heappush(heap,(table[p],p))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

class rode():
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return self.y < other.y
    def __gt__(self, other):
        return other > self
    def __le__(self, other):
        return not(other > self)
    def __ge__(self, other):
        return not(self > other)

n,m = map(int,input().split())
da = [[[i-1,0]] for i in range(n)]
da[0] = []
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
pq=[]
ju = [False for i in range(n)]
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, rode(i[0],i[1]))
while(len(pq)):
    now = heapq.heappop(pq)
    if now.x == n-1:
        print(now.y)
        sys.exit()
    if ju[now.x]:
        continue
    ju[now.x] = True
    for i in da[now.x]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,rode(i[0],now.y+i[1]))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

class rode():
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return self.y < other.y
    def __gt__(self, other):
        return other > self
    def __le__(self, other):
        return not(other > self)
    def __ge__(self, other):
        return not(self > other)

n,m = map(int,input().split())
da = [[[i-1,0]] for i in range(n)]
da[0] = []
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
for i in range(1,n):
    da[i].append([i-1,0])
pq=[]
ju = [False for i in range(n)]
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, rode(i[0],i[1]))
while(len(pq)):
    now = heapq.heappop(pq)
    if now.x == n-1:
        print(now.y)
        sys.exit()
    if ju[now.x]:
        continue
    ju[now.x] = True
    for i in da[now.x]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,rode(i[0],now.y+i[1]))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq

INF=10**12
def daik(s,g,d,adj):
    used=np.array([])
    heap=[]
    table=np.array([INF for i in range(N)])
    table[s]=0
    heapq.heappush(heap,(table[s],s))
    used=np.append(used,s)
                
    while heap and not(g in used):
        q=heapq.heappop(heap)
        a=q[1]
        used=np.append(used,a)
        for i in adj[a]:
            if not(i in used):
                table[i]=min(table[i],table[a]+d[a,i])
                heapq.heappush(heap,(table[i],i))
    return table[g]

N,M=map(int,input().split())
LRC=[]
for i in range(M):
    L,R,C=map(int,input().split())
    LRC.append([L-1,R-1,C])
LRC=np.array(LRC)
LRC=LRC[np.argsort(LRC[:,2])][::-1]

d=np.array([[INF for j in range(N)] for i in range(N)])
adj=[[] for i in range(N)]
for i in range(N-1):
    d[i+1,i]=0
    adj[i+1].append(i)
    adj[i].append(i+1)
for i in range(M):
    C=LRC[i,2]
    d[LRC[i,0],LRC[i,1]]=C
    d[LRC[i,1],LRC[i,0]]=C
    adj[LRC[i,0]].append(LRC[i,1])
    adj[LRC[i,1]].append(LRC[i,0])

ans=daik(0,N-1,d,adj)
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

class rode():
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return self.y < other.y
    def __gt__(self, other):
        return other > self
    def __le__(self, other):
        return not(other > self)
    def __ge__(self, other):
        return not(self > other)

n,m = map(int,input().split())
da = [[] for i in range(n)]
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
for i in range(1,n):
    da[i].append([i-1,0])
pq=[]
ju = [False for i in range(n)]
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, rode(i[0],i[1]))
while(len(pq)):
    now = heapq.heappop(pq)
    if now.x == n-1:
        print(now.y)
        sys.exit()
    if ju[now.x]:
        continue
    ju[now.x] = True
    for i in da[now.x]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,rode(i[0],now.y+i[1]))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq

INF=10**12
def daik(s,g,d,adj):
    used=np.array([])
    heap=[]
    table=np.array([INF for i in range(N)])
    table[s]=0
    heapq.heappush(heap,(table[s],s))
    used=np.append(used,s)
                
    while heap and not(g in used):
        q=heapq.heappop(heap)
        a=q[1]
        used=np.append(used,a)
        for i in adj[a]:
            if not(i in used):
                table[i]=min(table[i],table[a]+d[a,i] )
                heapq.heappush(heap,(table[i],i))
    return table[g]

N,M=map(int,input().split())
LRC=[]
for i in range(M):
    L,R,C=map(int,input().split())
    LRC.append([L-1,R-1,C])
LRC=np.array(LRC)
LRC=LRC[np.argsort(LRC[:,2])][::-1]

d=np.array([[INF for j in range(N)] for i in range(N)])
adj=[[] for i in range(N)]
for i in range(N-1):
    d[i+1,i]=0
    adj[i+1].append(i)
    adj[i].append(i+1)
for i in range(M):
    C=LRC[i,2]
    d[LRC[i,0],LRC[i,1]]=C
    d[LRC[i,1],LRC[i,0]]=C
    adj[LRC[i,0]].append(LRC[i,1])
    adj[LRC[i,1]].append(LRC[i,0])

ans=daik(0,N-1,d,adj)
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq

INF=10**12
def daik(s,g,d,adj):
    used=np.array([])
    heap=[]
    table=np.array([INF for i in range(N)])
    table[s]=0
    heapq.heappush(heap,(table[s],s))
    used=np.append(used,s)
                
    while heap and not(g in used):
        q=heapq.heappop(heap)
        a=q[1]
        used=np.append(used,a)
        for i in adj[a]:
            if not(i in used):
                cost=d[a,i] 
                if cost!=INF:
                    table[i]=min(table[i],table[a]+cost)
                    heapq.heappush(heap,(table[i],i))
    return table[g]

N,M=map(int,input().split())
LRC=[]
for i in range(M):
    L,R,C=map(int,input().split())
    LRC.append([L-1,R-1,C])
LRC=np.array(LRC)
LRC=LRC[np.argsort(LRC[:,2])][::-1]

d=np.array([[INF for j in range(N)] for i in range(N)])
adj=[[] for i in range(N)]
for i in range(N-1):
    d[i+1,i]=0
    adj[i+1].append(i)
    adj[i].append(i+1)
for i in range(M):
    C=LRC[i,2]
    d[LRC[i,0],LRC[i,1]]=C
    d[LRC[i,1],LRC[i,0]]=C
    adj[LRC[i,0]].append(LRC[i,1])
    adj[LRC[i,1]].append(LRC[i,0])

ans=daik(0,N-1,d,adj)
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

class rode():
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return self.y < other.y
    def __gt__(self, other):
        return other > self
    def __le__(self, other):
        return not(other > self)
    def __ge__(self, other):
        return not(self > other)

n,m = map(int,input().split())
da = [[] for i in range(n)]
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
for i in range(1,n):
    da[i].append([i-1,0])
pq=[]
ju = [False for i in range(n)]
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, rode(i[0],i[1]))
while(len(pq)):
    now = heapq.heappop(pq)
    if now.x == n-1:
        print(now.y)
        sys.exit()
    if ju[now.x]:
        continue
    ju[now.x] = True
    for i in da[now.x]:
        heapq.heappush(pq,rode(i[0],now.y+i[1]))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq

INF=10**12
# def daik(s,g,d):
#     used=np.array([])
#     heap=[]
#     table=np.array([INF for i in range(N)])
#     table[s]=0
#     heapq.heappush(heap,(table[s],s))
#     used=np.append(used,s)
                
#     while heap and not(g in used):
#         q=heapq.heappop(heap)
#         a=q[1]
#         used=np.append(used,a)
#         for i in range(N):
#             if not(i in used):
#                 cost=d[a,i] if a<=i else d[i,a]
#                 if cost!=INF:
#                     table[i]=min(table[i],table[a]+cost)
#                     heapq.heappush(heap,(table[i],i))
#     return table[g]

def daik(s,g,d):
    used=np.array([])
    heap=[]
    table=np.array([INF for i in range(N)])
    table[s]=0
    heapq.heappush(heap,(table[s],s))
    used=np.append(used,s)
                
    while heap and not(g in used):
        q=heapq.heappop(heap)
        a=q[1]
        used=np.append(used,a)
        for i in range(N):
            if not(i in used):
                cost=d[a,i] 
                if cost!=INF:
                    table[i]=min(table[i],table[a]+cost)
                    heapq.heappush(heap,(table[i],i))
    return table[g]

N,M=map(int,input().split())
LRC=[]
for i in range(M):
    L,R,C=map(int,input().split())
    LRC.append([L-1,R-1,C])
LRC=np.array(LRC)
LRC=LRC[np.argsort(LRC[:,2])][::-1]

d=np.array([[INF for j in range(N)] for i in range(N)])
# for i in range(N):
#     d[i,i]=0
# l=np.array([i+1 for i in range(N)])
# l[-1]=N
# for m in range(M):
#     L,R,C=LRC[m,0],LRC[m,1],LRC[m,2]
#     for i in range(L,R+1):
#         if l[i]<N:
#             d[i,l[i]:R+1]=C
#             l[i]=R+1
for i in range(N-1):
    d[i+1,i]=0
for i in range(M):
    C=LRC[i,2]
    d[LRC[i,0],LRC[i,1]]=C
    d[LRC[i,1],LRC[i,0]]=C
ans=daik(0,N-1,d)
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
N,M = [int(x) for x in input().split()]
path = np.array([[float("INF")]*(N) for _ in range(N)])
#path[:,0]=0
#path[0,:]=0
for i in range(M):
  a,b,c = [int(x) for x in input().split()]
  a = a-1
  b=b-1
  #path1 = np.copy(path)
  path[a:b+1,a:b+1]=np.minimum(path[a:b+1,a:b+1],c)
np.fill_diagonal(path,0)
d = dijkstra(path,indices = 0)
if d[N-1]==float("INF"):
  print(-1)
  exit()
print(int(d[N-1]))
#print(path.sum())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
N,M = [int(x) for x in input().split()]
path = np.array([[float("INF")]*(N) for _ in range(N)])
#path[:,0]=0
#path[0,:]=0
for i in range(M):
  a,b,c = [int(x) for x in input().split()]
  a = a-1
  b=b-1
  path1 = np.copy(path)
  path1[a:b+1,a:b+1]=c
  path = np.minimum(path,path1)
np.fill_diagonal(path,0)
d = dijkstra(path,indices = 0)
if d[N-1]==float("INF"):
  print(-1)
  exit()
print(int(d[N-1]))
#print(path.sum())

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M=map(int,input().split())
path=[[float("inf")]*N for i in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

dist=[float("inf")]*N
dist[0]=0
q=[[dist[i],i] for i in range(N)]
heapq.heapify(q)

while q:
  d,ind=heapq.heappop(q)
  if d<=dist[ind]:
    for i in range(N):
      if ind>=i:p=0
      else:p=path[ind][i]
      if dist[i]>d+p:
        dist[i]=d+p
        heapq.heappush(q,[dist[i],i])

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M=map(int,input().split())
path=[[0 if i<=j else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

dist=[float("inf")]*N
dist[0]=0
q=[[dist[i],i] for i in range(N)]
heapq.heapify(q)

while q:
  d,ind=heapq.heappop(q)
  if d<=dist[ind]:
    for i in range(N):
      if dist[i]>d+path[ind][i]:
        dist[i]=d+path[ind][i]
        heapq.heappush(q,[dist[i],i])

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

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
path=[[0 if i<=j else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

seen=[0]*N
dist=[float("inf")]*N
dist[0]=0
v=-1
while v!=N-1:
  v=-1
  for i in range(N):
    if seen[i]==0 and v==-1:
      v=i
    if seen[i]==0 and dist[i]<dist[v]:
      v=i
  seen[v]=1
  for i in range(N):
    dist[i]=min(dist[v]+path[v][i],dist[i])
    
if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
path=[[0 if i<=j else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

seen=[]
dist=[float("inf")]*N
dist[0]=0
v=-1
while v!=N-1:
  v=-1
  for i in range(N):
    if i not in seen and v==-1:
      v=i
    if i not in seen and dist[i]<dist[v]:
      v=i
  seen.append(v)
  for i in range(N):
    dist[i]=min(dist[v]+path[v][i],dist[i])
    
if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])

Submission status: Time Limit Exceeded

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

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
    
d = dijkstra(0, N, M, NN)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq

INF=10**12
def daik(s,g,d):
    used=np.array([])
    heap=[]
    table=np.array([INF for i in range(N)])
    table[s]=0
    heapq.heappush(heap,(table[s],s))
    used=np.append(used,s)
                
    while heap and not(g in used):
        q=heapq.heappop(heap)
        a=q[1]
        used=np.append(used,a)
        for i in range(N):
            if not(i in used):
                cost=d[a,i] if a<=i else d[i,a]
                if cost!=INF:
                    table[i]=min(table[i],table[a]+cost)
                    heapq.heappush(heap,(table[i],i))
    return table[g]


N,M=map(int,input().split())
LRC=[]
for i in range(M):
    L,R,C=map(int,input().split())
    LRC.append([L-1,R-1,C])
LRC=np.array(LRC)
LRC=LRC[np.argsort(LRC[:,2])]

d=np.array([[INF for j in range(N)] for i in range(N)])
for i in range(N):
    d[i,i]=0
l=np.array([i+1 for i in range(N)])
l[-1]=N
for m in range(M):
    L,R,C=LRC[m,0],LRC[m,1],LRC[m,2]
    for i in range(L,R+1):
        if l[i]<N:
            d[i,l[i]:R+1]=C
            l[i]=R+1

ans=daik(0,N-1,d)
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq

INF=10**12
def daik(s,g,d):
    used=np.array([])
    heap=[]
    table=np.array([INF for i in range(N)])
    table[s]=0
    a=s
    used=np.append(used,a)
    for i in range(N):
        if i!=a and not(i in used):
            cost=d[a,i] if a<=i else d[i,a]
            if cost!=INF:
                table[i]=min(table[i],table[a]+cost)
                heapq.heappush(heap,(table[i],i))
    while heap:
        q=heapq.heappop(heap)
        a=q[1]
        used=np.append(used,a)
        for i in range(N):
            if i!=a and not(i in used):
                cost=d[a,i] if a<=i else d[i,a]
                if cost!=INF:
                    table[i]=min(table[i],table[a]+cost)
                    heapq.heappush(heap,(table[i],i))
    return table[g]


N,M=map(int,input().split())
LRC=[]
for i in range(M):
    L,R,C=map(int,input().split())
    LRC.append([L-1,R-1,C])
LRC=np.array(LRC)
LRC=LRC[np.argsort(LRC[:,2])]

d=np.array([[INF for j in range(N)] for i in range(N)])
for i in range(N):
    d[i,i]=0
l=np.array([i+1 for i in range(N)])
l[-1]=N
for m in range(M):
    L,R,C=LRC[m,0],LRC[m,1],LRC[m,2]
    for i in range(L,R+1):
        if l[i]<N:
            d[i,l[i]:R+1]=C
            l[i]=R+1

ans=daik(0,N-1,d)
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

n,m = map(int, input().split())
t = sorted([tuple(map(int, input().split())) for i in range(m)])
d=[0,0]+[1e18]*n
for l,r,c in t:
  for i in range(r,l,-1):
    if d[l]+c<d[i]:
      d[i]=d[l]+c
    else:
      break
print(d[-2]%10**18or-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
sys.setrecursionlimit(10**7)
n, m = [int(i) for i in sys.stdin.readline().split()]
INF = 10**9
graph = [[1e-10 if j - i == 1 else 0 for i in range(n)] for j in range(n)]
for i in range(m):
    l, r, c = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    graph[l][r] = c
    graph[r][l] = c
graph = csr_matrix(graph)
res = dijkstra(graph, indices=[0])
print(int(res[0][-1]) if res[0][-1] < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
sys.setrecursionlimit(10**7)
n, m = [int(i) for i in sys.stdin.readline().split()]
INF = 10**9
graph = [[1e-10 if j - i == 1 else INF for i in range(n)] for j in range(n)]
for i in range(m):
    l, r, c = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    graph[l][r] = c
    graph[r][l] = c
graph = csr_matrix(graph)
res = dijkstra(graph, indices=[0])
print(int(res[0][-1]) if res[0][-1] < INF else -1)