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: Runtime Error

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)]
print(adj)
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])
adj=np.unique(adj,axis=1)
print(adj)
ans=daik(0,N-1,d,adj)
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

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)
print(int(d[N-1]))
#print(path.sum())

Submission status: Runtime Error

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


n, m = map(int, input().split())
ro = [[float("inf") for i in range(n)] for i in range(n)]
lis = [[int(i) for i in input().split(" ")] for i in range(m)]
for i in lis:
    ro[i[0]][i[1]] = i[2]

cost = ro         
te = dijkstra(0,n,n-1,cost)
if te[-1] == float("inf"):
    print(-1)
else:
    print(te[-1])

Submission status: Runtime Error

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)])
INF = 10 ** 18
dp = [0] + [INF] * (n-1) # 頂点1から、各頂点(1~n)までの最短距離
for l,r,c in t:
  for i in range(r,l,-1):
    if dp[l] + c < dp[i]:
      dp[i] = dp[l] + c
    else:
      break
ans = dp[n-1]
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
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 = np.ones(shape=(n,n)) * INF
for i in range(m):
    l, r, c = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    graph[l][:r+1] = np.where(graph[l][:r+1] < c, graph[l][:r+1], np.ones_like(graph[l][:r+1]) * c)
graph = np.where(graph == INF, np.zeros_like(graph), graph)
graph = csr_matrix(graph)
res = dijkstra(graph, indices=[0])
print(int(res[0][-1]) if res[0][-1] < INF else -1)

Submission status: Runtime Error

Solution code:
#O(ElogV)
import heapq
def dijkstra_heap(s,g):
    used = [True] * n #True:未確定
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,[[0,e[0]],e[1]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        if v==g:
            return (minedge[0][0]+1)*k
        nl = minedge[0][1]
        kai=minedge[0][0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                if e[0]==nl:
                    heapq.heappush(edgelist,[[kai,e[0]],e[1]])
                else:
                    heapq.heappush(edgelist,[[kai+1,e[0]],e[1]])
                    
    return -1

################################
n,m = map(int,input().split()) #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
l=[]
for i in range(m):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])
    l.append([x-1,y-1])
zeroedge=[0]*n
l.sort()
l.append([10**10,10**10+1])
i=0
nl=l[i][0]
r=l[i][1]
while i<n+1:
    if l[i][0]>r:
        for j in range(nl,r):
            edge[j+1].append([0,j])
        nl=l[i][0]
        r=l[i][1]
        i+=1
    else:
        r=max(r,l[i][1])
        i+=1       
print(dijkstra_heap(0,n-1))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
n, m = [int(i) for i in sys.stdin.readline().split()]
INF = 10**9
graph = np.ones(shape=(n,n)) * INF
for i in range(m):
    l, r, c = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    graph[l][:r+1] = np.where(graph[l][:r+1] < c, graph[l][:r+1], np.ones_like(graph[l][:r+1]) * c)
graph = np.where(graph == INF, np.zeros_like(graph), graph)
graph = csr_matrix(graph)
res = dijkstra(graph, indices=[0])
print(int(res[0][-1]) if res[0][-1] < INF else -1)

Submission status: Runtime Error

Solution code:
INF = 2**31 - 1

class RangeMinimunQuery:
    def __init__(self, n):
        self._n = 1
        while self._n < n:
             self._n *= 2
        self._d = [INF] * (2 * self._n)

    def update(self, k, v):
        k += self._n
        self._d[k] = v
        k >>= 1
        while k:
            self._d[k] = min(self._d[2 * k], self._d[2 * k + 1])
            k >>= 1

    def query(self, l, r):
        l += self._n
        r += self._n
        res = INF
        while l < r:
            if l & 1:
                res = min(res, self._d[l])
                l += 1
            if r & 1:
                r -= 1
                res = min(res, self._d[r])
            l >>= 1
            r >>= 1
        return res

    def a(self, k):
        return self._d[k + self._n]

    def d(self):
        return self._d[self._n:]

n, m = map(int, raw_input().split())
edges = []
for _ in range(m):
    edges.append(map(int, raw_input().split()))
edges.sort()

segtree = RangeMinimunQuery(n)
segtree.update(1, 0)
for l, r, c in edges:
    cost = min(segtree.query(l, r) + c, segtree.a(r))
    segtree.update(r, cost)

if segtree.a(n) == INF:
    print -1
else:
    print segtree.a(n)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import shortest_path
import numpy as np

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
 

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

inf = 10**15

g = np.full((n, n), inf)

for i in range(m):
    l, r, c = map(int,input().split())
    np.minimum(g[l-1:r, l-1:r], c, out = g[l-1:r, l-1:r])

ans = shortest_path(g, directed = False)[0, n-1]
if ans > 10**14:
	print(-1)
else:
	print(int(ans))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import shortest_path
import numpy as np

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
 

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

inf = 10**15

g = np.full((n+1, n+1), inf)

for i in range(m):
    l, r, c = map(int,readline().split())
    g[l-1:r, l-1:r] = np.minimum(g[l-1:r, l-1:r], c)
    
print(g)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')

# 一点更新　区間取得　1-indexed
class SegmentTree:
    def __init__(self, n):
        tmp = 1
        while tmp < n:
            tmp <<= 1
        # self.N : 完全二分木の葉の数(N以上の最小の2べき)
        self.N = tmp
        # 2*self.N - 1 : 完全二分木のノード数
        # 1-indexedで管理するので１つ余分に設ける
        self.Data = [(inf, -1) for _ in range(2*self.N)]

    # k (0-indexed)
    def update(self, k, x):
        #　インデックスを補正
        k += self.N
        # 指定ノードを更新
        self.Data[k] = x
        # kを含む区間ノードを更新していく
        while k > 1:
            k >>= 1
            self.Data[k] = min([self.Data[2*k], self.Data[2*k+1]])

    # [l, r) (0-indexed)
    def query(self, l, r):
        #　インデックスを補正
        l += self.N
        r += self.N
        # 返り値を初期化
        res = [inf, -1]
        while l < r:
            # 右側なら右側を更新 右上に行く
            # 左側なら更新しない　上に行く
            if l & 1:
                res = min([res, self. Data[l]])
                l += 1
            # 右側なら左側を更新　上に行く
            # 左側なら更新しない 上に行く
            if r & 1:
                r -= 1
                res = min([res, self.Data[r]])
            l >>= 1; r >>= 1
        return res

    def value(self, k):
        return st.query(k, k+1)

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

C = [(a, b) for a, b in zip(A, B)]
C = sorted(C, key=lambda x:(x[1], x[0]))
A = [c[0] for c in C]
B = [c[1] for c in C]

st = SegmentTree(N)
for i, a in enumerate(A):
    st.update(i, [a, i])

ans = 0
for i, b in enumerate(B):
    a = st.value(i)[0]
    if a <= b:
        pass
    else:
        # 見ているところより右から最小のものを選んでくる
        v, vi = st.query(i, N)
        if not v <= b:
            print("No")
            exit()
        st.update(i, [vi, i])
        st.update(vi, [b, vi])
        ans += 1

if ans <= N-2:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import shortest_path
import numpy as np

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
 

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

inf = 10**15

g = np.full((n+1, n+1), inf)

for i in range(m):
    l, r, c = map(int,readline().split())
    g[l-1:r, l-1:r] = np.minimum(g[l-1:r, l-1:r], c)

ans = shortest_path(g, directed = False)[0, n-1]
if ans > 10**14:
	print(-1)
else:
	print(int(ans))

Submission status: Runtime Error

Solution code:

from scipy.sparse.csgraph import shortest_path
import numpy as np

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
 

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

inf = 10**15

g = np.full((n, n), inf)

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

ans = shortest_path(g, directed = False)[(0, n-1)]
if ans > 10**14:
	print(-1)
else:
	print(int(ans))

Submission status: Runtime Error

Solution code:

from scipy.sparse.csgraph import shortest_path
import numpy as np

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
 

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

inf = 10**15

g = np.full((n, n), inf)

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

ans = shortest_path(g, directed = False)[(0, n-1)]
if ans > 10**14:
	print(-1)
else:
	print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
inf = (10) ** 10
n, m = list(map(int, input().split()))

graph = np.full((n+1,n+1), inf)
for i in range(1,n+1):
    graph[i][i - 1] = 0.0001
for i in range(m):
    l, r, c = list(map(int, input().split()))
    graph[l][r] = min(graph[l][r],  c)
    graph[r][l] = min(graph[r][l],  c)
graph = dijkstra(csr_matrix(graph))

if graph[1][n] == inf:
    print(-1)
else:
    print(int(graph[1][n]))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
inf = (10.0) ** 10
n, m = list(map(int, input().split()))

graph = np.full((n+1,n+1), inf)
for i in range(1,n+1):
    graph[i][i - 1] = 0.0001
for i in range(m):
    l, r, c = list(map(int, input().split()))
    graph[l][r] = min(graph[l][r],  c)
    graph[r][l] = min(graph[r][l],  c)
graph = dijkstra(csr_matrix(graph))

if graph[1][n] == inf:
    print(-1)
else:
    print(int(graph[1][n]))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
inf = (10.0) ** 2
n, m = list(map(int, input().split()))

graph = np.full((n+1,n+1), inf)
for i in range(1,n+1):
    graph[i][i - 1] = 0.0001
for i in range(m):
    l, r, c = list(map(int, input().split()))
    graph[l][r] = min(graph[l][r],  c)
    graph[r][l] = min(graph[r][l],  c)
graph = dijkstra(csr_matrix(graph))

if graph[1][n] == inf:
    print(-1)
else:
    print(int(graph[1][n]))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
import itertools
from scipy.sparse import csr_matrix
inf = (10.0) ** 2
n, m = list(map(int, input().split()))

graph = np.full((n+1,n+1), inf)
for i in range(1,n+1):
    graph[i][i - 1] = 0.0001
for i in range(m):
    l, r, c = list(map(int, input().split()))
    graph[l][r] = min(graph[l][r],  c)
    graph[r][l] = min(graph[r][l],  c)
graph = dijkstra(graph)

if graph[1][n] == inf:
    print(-1)
else:
    print(int(graph[1][n]))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
import itertools
from scipy.sparse import csr_matrix
inf = (10.0) ** 2
n, m = list(map(int, input().split()))

graph = np.full((n+1,n+1), inf)
graph[2][2] = 0.0001
for i in range(1,n+1):
    graph[i][i - 1] = 0.01
    graph[i][i] = 0
for i in range(m):
    l, r, c = list(map(int, input().split()))
    graph[l][r] = min(graph[l][r],  c)
    graph[r][l] = min(graph[r][l],  c)
graph = dijkstra(graph)

if graph[1][n] == inf:
    print(-1)
else:
    print(int(graph[1][n]))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
import itertools
from scipy.sparse import csr_matrix
np.set_printoptions(precision=10)
inf = (10.0) ** 2
n, m = list(map(int, input().split()))

graph = np.full((n+1,n+1), inf)
graph[2][2] = 0.0001
for i in range(1,n+1):
    graph[i][i - 1] = 0.01
    graph[i][i] = 0
for i in range(m):
    l, r, c = list(map(int, input().split()))
    graph[l][r] = min(graph[l][r],  c)
    graph[r][l] = min(graph[r][l],  c)
graph = dijkstra(graph)

if graph[1][n] == inf:
    print(-1)
else:
    print(int(graph[1][n]))

Submission status: Runtime Error

Solution code:
import sys


class AlgSegmentTreeMin:
    def __init__(self, n, default_value):
        self.Nelem = n
        self.default_value = default_value
        self.size = 1 << (n.bit_length())
        self.data = [self.default_value] * (2 * self.size)

    def build(self, raw_data):
        # raw_data は 0-indexed
        for i, x in enumerate([self.default_value] * (self.Nelem + 1)):
            self.data[self.size + i] = x
        for i in range(self.size - 1, 0, -1):
            x = self.data[i + i];
            y = self.data[i + i + 1]
            self.data[i] = x if x < y else y

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i + i]
            y = self.data[i + i + 1]
            self.data[i] = min(x, y)
            i >>= 1

    def get_value(self, left, right):
        left += self.size
        right += self.size + 1
        x = self.default_value
        while left < right:
            if left & 1:
                y = self.data[left]
                x = min(x, y)
                left += 1
            if right & 1:
                right -= 1
                y = self.data[right]
                x = min(x, y)
            left >>= 1
            right >>= 1
        return x


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    stree = AlgSegmentTreeMin(n, 10 ** 15)
    stree.build()
    lrc = [list(map(int, readline().split())) for _ in range(m)]
    lrc.sort()
    stree.update(0, 0)
    for l, r, c in lrc:
        l -= 1
        r -= 1
        tm = stree.get_value(l, r)
        now = stree.get_value(r, r)
        tm = tm + c if tm + c < now else now
        stree.update(r, tm)
    mt = stree.get_value(n-1, n)
    print(mt if mt != stree.default_value else -1)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys


class AlgSegmentTreeMin:
    def __init__(self, n, default_value):
        self.Nelem = n
        self.default_value = default_value
        self.size = 1 << (n.bit_length())
        self.data = [default_value] * (2 * self.size)

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i + i]
            y = self.data[i + i + 1]
            self.data[i] = min(x, y)
            i >>= 1

    def get_value(self, left, right):
        left += self.size
        right += self.size + 1
        x = self.default_value
        while left < right:
            if left & 1:
                y = self.data[left]
                x = min(x, y)
                left += 1
            if right & 1:
                right -= 1
                y = self.data[right]
                x = min(x, y)
            left >>= 1
            right >>= 1
        return x


def solve():
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().split()))
    stree = AlgSegmentTreeMin(n, 10 ** 15)
    m = map(int, read().split())
    lrc = zip(m, m, m)
    lrc.sort()
    stree.update(0, 0)
    for l, r, c in lrc:
        l -= 1
        r -= 1
        tm = stree.get_value(l, r)
        now = stree.get_value(r, r)
        tm = tm + c if tm + c < now else now
        stree.update(r, tm)
    mt = stree.get_value(n-1, n)
    print(mt if mt != stree.default_value else -1)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
Glaph = [[0 for j in range(N)] for i in range(N)]
for i in range(M):
  l,r,c = map(int,input().split())
  l -= 1
  r -= 1
  for s in range(l,r+1):
    if Glaph[s][s+1] == 0 or Glaph[s][s+1] > c:
      Glaph[s][s+1] = c

def djikstra(s,g,Glaph):
  INF = 1000000
  done = [ 0  for i in range(N)]
  cost = [INF for i in range(N)]
    
  done[s] = 1
  cost[s] = 0
  done_node = s
  
  for i in range(N):
    min = INF
   
    k = done_node 
    for j in range(N):
      if done[j] == 0:
        
        if Glaph[k][j] != 0 and cost[j] > cost[k] + Glaph[k][j]:
          cost[j] = cost[k] + Glaph[k][j]
        
        if min > cost[j]:
          min = cost[j]
          done_node = j
     
    done[done_node] = 1
    if done_node == g:
      break
  
  if cost[g] == INF:
    return(-1)
  else:
    return cost[g]
 
      
print(djikstra(0,N-1,Glaph))

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
route_list = [[] for _ in range(N)]
for i in range(M):
    L, R, C = map(int, input().split())
    route_list[L-1].append((R-1, C))
for i in range(N-1):
    route_list[i+1].append((i, 0))

distance = [float("inf")] * node_num
distance[0] = 0  # 初期のノードの距離は0とする
q = [(0, 0)]

while q:
    _, u = heappop(q)
    for des, cost in route_list[u]:
        if distance[des] > distance[u] + cost:
            distance[des] = distance[u] + cost
            heappush(q, (distance[des], des))

print(distance[-1] if distance[-1] != float("inf") else -1)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
node_num = N
route_list = [[] for _ in range(N)]
for i in range(M):
    L, R, C = map(int, input().split())
    route_list[L-1].append((R-1, C))
for i in range(N-1):
    route_list[i+1].append(i)

distance = [10**9] * node_num
distance[0] = 0  # 初期のノードの距離は0とする
q = [(0, 0)]
 
while q:
    _, u = heappop(q)
    for des, cost in route_list[u]:
        if distance[des] > distance[u] + cost:
            distance[des] = distance[u] + cost
            heappush(q, (distance[des], des))
 
print(distance[-1] if distance[-1] != 10**9 else -1)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]
pb = [(bi,i) for i,bi in enumerate(b)]

sa = sorted(a)
sb = sorted(b)
pb.sort()

na = [a[i] for bi,i in pb]


ok = 1
for i,j in zip(sa,sb):
    if i > j: ok = 0

for i,j in zip(sa[1:],sb):
    if i <= j: break
else:
    #sa => na が巡回置換か？
    d = {ai:i for i,ai in enumerate(sa)}
    ra = [d[ai] for ai in na]
    
    #print(ra,ok)    
    now = 0
    for i in range(n-1):
        now = ra[now]
        #print(now)
        if now == 0:
            break
    else: ok = 0    


    

#print(a,b,sa,sb,na)

if ok: print("Yes")    
else: print("No")

Submission status: Runtime Error

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



def dijkstra(repn, start, goal):
    dist = [inf for i in range(N + 1)] # 始点から各頂点までの最短距離を格納する
    
    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 repn[src].values():
            cost = repn[src][dest]
            if dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost # distの更新
                heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                
    return dist[goal]
        



N, M = map(int, input().split())
repn = [defaultdict(list) for _ in range(N + 1)]
for i in range(2, N + 1):
    repn[i][i - 1] = 0
for _ in range(M):
    l, r, c = map(int, input().split())
    if repn[l][r] == [] or repn[l][r] > c: #つまずきポイントその１
        repn[l][r] = c

d = dijkstra(repn, 1, N)

if d == inf:
    print(-1)
else:
    print(d)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

n, m = [int(x) for x in input().split()]
v = [ {} for x in range(n - 1)]
for i in range(m):
    (l, r, c) = [int(x) for x in input().split()]
    for a in range((l - 1), r, 1):
        for b in range((a + 1), r, 1):
            if (b in v[a]):
                if v[a][b] > c:
                    v[a][b] = c
            else:
                v[a][b] = c

def dp(v, st, end):
    if st == end:
        return 0
    elif v[st] == {}:
        return 10**20
    else:
        z = 10**20
        for k in v[st].keys():
            t = v[st][k] + dp(v, k, end)
            if z > t:
                z = t
        return z
            
cost = dp(v, 0, n-1)
print(cost if cost < 10**20 else -1)

Submission status: Runtime Error

Solution code:
n, m = [int(x) for x in input().split()]
v = [ {} for x in range(n - 1)]
for i in range(m):
    (l, r, c) = [int(x) for x in input().split()]
    for a in range((l - 1), r, 1):
        for b in range((a + 1), r, 1):
            if (b in v[a]):
                if v[a][b] > c:
                    v[a][b] = c
            else:
                v[a][b] = c

def dp(v, st, end):
    if st == end:
        return 0
    elif v[st] == {}:
        return 10**20
    else:
        z = 10**20
        for k in v[st].keys():
            t = v[st][k] + dp(v, k, end)
            if z > t:
                z = t
        return z
            
cost = dp(v, 0, n-1)
print(cost if cost < 10**20 else -1)

Submission status: Runtime Error

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

class RangeUpdateQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        self.INF = 10 ** 18
        self.data = [self.INF]*(2*self.n0-1)

    def update(self, l,r,v):
        l += self.n0
        r += self.n0
        while l < r:
            if r&1:
                r -= 1
                if self.data[r-1] > v:
                    self.data[r-1] = v
            if l&1:
                if self.data[l-1] > v:
                    self.data[l-1] = v
                l += 1
            l >>=1
            r >>=1

    def query(self, i):
        i += self.n0-1
        res = self.INF
        while i+1:
            if self.data[i] < res:
                res = self.data[i]
            i = ~-i//2
        return res

n,m = map(int, input().split())
light = [list(map(int, input().split())) for i in range(m)]
light.sort()
RUQ = RangeUpdateQuery(n-1)
RUQ.update(0,1,0)
for a,b,c in light:
    cur = RUQ.query(a-1)
    RUQ.update(a, b, cur+c)

ans = RUQ.query(n-1)
if ans >= 10 ** 18:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

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(m):
    l,r,z = map(int,input().split())
    cost[i+1][i] = 0
    cost[l-1][r-1] = z
    cost[r-1][l-1] = z
ret = dijkstra(0,n,n+m-1,cost)
if (ret[-1] == 'inf'):
    print(-1)
else:
    print(ret[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
a = np.full((N, N), 10**15)
for _ in range(M):
    L, R, C = map(int, input().split())
    a[L - 1:R, L - 1:R] = np.minimum(a[L - 1:R, L - 1:R], C)
print(1)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
a = np.full((N, N), 10**15)
for _ in range(M):
    L, R, C = map(int, input().split())
    a[L - 1:R, L - 1:R] = np.minimum(a[L - 1:R, L - 1:R], C)

indices_diagonal = np.diag_indices(N)
a[indices_diagonal] = 0

d = dijkstra(a)
print(1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
MOD = 998244353

n = int(input())
d = list(map(int, input().split()))

cnt = defaultdict(int)
m = 0
for i in range(n):
    cnt[d[i]] += 1
    m = max(d[i], m)

if d[0] != 0 or cnt[0] != 1:
    ans = 0
else:
    ans = 1
    for i in range(1, m + 1):
        ans *= cnt[i - 1]**cnt[i]
        ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
MOD = 998244353

n = int(input())
d = list(map(int, input().split()))

cnt = defaultdict(int)
m = 0
for i in range(n):
    cnt[d[i]] += 1
    m = max(d[i], m)

if d[0] != 0 or dd[0] != 1:
    ans = 0
else:
    ans = 1
    for i in range(1, m + 1):
        ans *= cnt[i - 1]**cnt[i]
        ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
a = np.full((N, N), 10**15)
for _ in range(M):
    L, R, C = map(int, input().split())
    a[L - 1:R, L - 1:R] = np.minimum(a[L - 1:R, L - 1:R], C)

indices_diagonal = np.diag_indices(N)
a[indices_diagonal] = 0
print(1)

Submission status: Runtime Error

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for i in range(N)]
    for i in range(1, N):
        Edge[i].append((0, i - 1))
    for _ in range(M):
        L, R, C = map(int, input().split())
        Edge[L-1].append((C, R-1))
    
    Dist = [-1] * N
    Q = []
    heapify(Q)
    heappush((0, 0))
    while Q:
        nowcost, nownode = heappop(Q)
        if Dist[nownode] == -1:
            Dist[nownode] = nowcost
            for addcost, nextnode in Edge[nownode]:
                if Dist[nownode] == -1:
                    heappush(Q, (nowcost + addcost, nextnode))
    print(Dist[N-1])

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop

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

LRC = [[int(x) for x in input().split()] for _ in range(L)]
LRC.sort() # Lの昇順

LRC

# [l,r]を使うなら、その時点での最安値と噛み合わせる

q = [(0,1)] # (コスト、右端)
for left,right,cost in LRC:
    while True:
        if len(q)==0:
            print(-1)
            exit()
        x,y = q[0]
        if y < left:
            heappop(q)
            continue
        break
    heappush(q,(x+cost,right)) 

while q:
    x,y = heappop(q)
    if y != N:
        continue
    answer = x
    break

print(answer)

Submission status: Runtime Error

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
N,M=map(int, input().split())
graph=np.full((N,N),999999999,int)
for _ in range(M):
    A,B,C=map(int, input().split())
    for i in range(A-1,B-1):
        for j in range(i+1,B):
            graph[i,j]=min(C,graph[i,j])
            graph[j,i]=min(C,graph[j,i])
for i in range(N):
    graph[i,i]=0
    
graph = csr_matrix(graph)
print(int(floyd_warshall(csgraph=graph)[0,N-1]))
# print(int(dist_matrix))