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
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)
if d[0, N - 1] > 10**14:
    print(-1)
else:
    print(int(d[0, N - 1]))

Submission status: Runtime Error

Solution code:
import numpy as np
import collections
import sys
N, M  = map(int, input().split(' '))
graph = np.ones((N, N), dtype=int) + 1e9
for i in range(M):
    L, R, C = map(int, input().split(' ')[:3])
    graph[L-1:R, L-1:R] = np.where(graph[L-1:R, L-1:R] > C, C, graph[L-1:R, L-1:R])
Ds = np.zeros(N, dtype=int)
for i in range(N-2, -1, -1):
    Ds[i] = (Ds[i+1:] + graph[i, i+1:]).min()
print(int(Ds[0]) if Ds[0] <= 1e9 else -1)

Submission status: Runtime Error

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
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)
dist_matrix, predecessors = dijkstra(csgraph=graph, directed=False, return_predecessors=True)
print(int(dist_matrix[0,N-1]))

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<set>
#include<vector>
using namespace std;
#define ll long long

class P {
public:
  ll L, R, C;
  P(ll _L, ll _R, ll _C): L(_L),R(_R),C(_C) {}
};

struct cmp_L { bool operator()(const P x, const P y) const { return x.L < y.L; } } Cmp_L;
struct cmp_R { bool operator()(const P x, const P y) const { return x.R < y.R; } } Cmp_R;
struct cmp_C { bool operator()(const P x, const P y) const { return x.C < y.C; } } Cmp_C;

int main(){
  ll N, M;
  cin >> N >> M;

  multiset<P, cmp_L> Plist;
  multiset<P, cmp_C> Qlist;
  for(ll m=0; m<M; ++m) {
    ll L, R, C;
    P p(L,R,C);
    Plist.insert(p);
  }

  ll i=1;
  vector<ll> M(N+1);
  M[1]=0;

  while(i<N){
    for(ll ip=0; ip<P.size() && P[ip].L<=i; ++i){
      auto p = P.begin();
      P q(*p);
      q.C += M[q.L];
      Q.insert(q);
      P.erase(p);
    }

    for(auto itr = Q.begin(); itr!=Q.end(); ++itr){
      if(itr->R>i) break;
      Q.erase(itr);
    }

    if(Q.size()==0){ cout << -1 << endl; return 0; }
    
    auto qq = Q.begin();
    for(ll r=i+1; r<qq->R+1; ++r){
      M[r] = qq->C;
    }
    i = r;
  }

  cout << M[N]<<endl;

  return 0;
}

Submission status: Runtime Error

Solution code:
def find(index, N) :
  max_cnt = 0
  next_N = L[index]
  if next_N == 1 :
    # print(C[index])
    return C[index]
  next_index = [j for j, x in enumerate(R) if x >= next_N and x < N]
  if not next_index :
    return 1000000000
  if len(next_index) > 1 :
    for k in range(len(next_index)) :
      cnt = 0
      cnt += C[index]
      cnt += find(next_index[k], next_N)
      if max_cnt > cnt or k == 0:
        max_cnt = cnt
  else :
    max_cnt += C[index]
    # tmp = find(next_index[0], next_N)
    # print(next_index[0],tmp)
    max_cnt += find(next_index[0], next_N)
  return max_cnt

N, M = map(int, input().split())
L = []
R = []
C = []
max_cnt = 10
for i in range(M) :
  tmp = list(map(int, input().split()))
  L.append(tmp[0])
  R.append(tmp[1])
  C.append(tmp[2])

index = [i for i, x in enumerate(R) if x == N]
if not index :
  print(-1)
  exit()
if len(index) > 1 :
  for i in range(len(index)) :
    cnt = 0
    cnt = find(index[i], N)
    if max_cnt > cnt or i == 0:
      max_cnt = cnt
else :
  max_cnt = find(index[0],N)

if max_cnt = 1000000000 :
  print(-1)
else :
  print(max_cnt)

Submission status: Runtime Error

Solution code:
import math
from collections import deque
N,M = map(int,input().split())
route_list = [[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 j in range(l,r+1):
    for k in range(j+1,r+2):
      route_list[j][k] = c
      route_list[k][j] = c

node_num = len(route_list) #ノードの数

unsearched_nodes = list(range(node_num)) # 未探索ノード
distance = [float('inf')] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0 # 初期のノードの距離は0とする

# @GDaigo さんのコメントより関数の追加 2017/03/18
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = float('inf') # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance[node_index]: 
            posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_list[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新

# 以下で結果の表示


previous_node = node_num - 1
while previous_node != -1:
    previous_node = previous_nodes[previous_node]
if distance[node_num - 1] != float("inf"):
  print(distance[node_num - 1])
else:
  print(-1)

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

G = None 
N = None

def dij(s):
    global G,N
    d = [sys.maxsize]*(N+1)
    color = [sys.maxsize]*(N+1)

    d[1] = 0
    d[1] = "gray"

    while True:
        minv = sys.maxsize
        u = -1
        for i in range(1,N+1):
            if minv > d[i] and color[i] != "black":
                u - i
                minv = d[i]
        if u == -1:
            break
        color[u] = "black"
        for v in range(1,N+1):
            if color[v] != "black" and G[u][v] != sys.maxsize:
                if d[v] > d[u] + G[u][v]:
                    d[v] = d[u] + G[u][v]
                    color[v] = "gray"

    return d[N]

def main():
    global G,N
    N,M = map(int, input().split())
    G = [[0]*(N+1) for _ in range(N+1)]
    LRC = [tuple(map(int, input().split())) for _ in range(M)]
    for L,R,C in LRC:
        for s in range(L,R):
            for t in range(s+1,R+1):
                if G[s][t]:
                    G[s][t] = min(C,G[s][t])
                    G[t][s] = min(C,G[t][s])
                else:
                    G[s][t] = C
                    G[t][s] = C
    print(dij(1))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
graph = np.zeros((N, N))
for i in range(M):
    L, R, C = map(int, input().split())
    for s in range(L, R):
        for t in range(s+1, R+1):
            point = graph[s-1][t-1]
            if (point == 0.):
                graph[s-1][t-1] = C
            if C < graph[s-1][t-1]:
                graph[s-1][t-1] = C
print(int(shortest_path(csr_matrix(graph), indices=0, directed=False, method='BF')[-1]))

Submission status: Runtime Error

Solution code:
import pandas as pd
import sys

N, M = map(int, input().split())
L = []
R = []
C = []
for m in range(M):
    l,r,c = map(int, input().split())
    L.append(l)
    R.append(r)
    C.append(c)

data = pd.DataFrame({"L":L, "R":R, "C":C})
position = 1
min_c = 0
while True:
    data_tmp = data[(data["L"] <= position) & (data["R"] > position)]
    if len(data_tmp)==0:
        print(-1)
        break
        
    min_c_tmp = data_tmp["C"].min()
    min_c += min_c_tmp
    position = data_tmp[data_tmp["C"]==min_c_tmp]["R"].max()

    if position == N:
        print(min_c)
        break

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 10
LRC.sort(key=lambda x: x[2], reverse=True)
LRC.sort()
dp = [INF] * (N+1) # dp[0]は使わない
dp[1] = 0
for l, r, c in LRC:
    x = dp[l] + c
    for i in range(r+1, l-1, -1):
        if dp[i] > x:
            dp[i] = x
        else:
            break
if dp[N] == INF:
    print(-1)
else:
    print(dp[N])

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.ones(n, dtype=np.int) * (c.sum() + 1)
dp[0] = 0
active = np.zeros(n, dtype=np.bool)
active[0] = True
while np.any(active):
  act = np.argmax(active)
  use = (l <= act) * (r > act)
  dp[r] = np.minimum(np.min(dp[r[use]] + c[use]), dp[r])
  active[act] = False
  
if dp[-1] > c.sum():
  print(-1)
else:
  print(dp[-1])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
LRC=sorted([list(map(int,input().split())) for i in range(M)])
d=[10**15]*N
d[0]=0
import sys
sys.setrecursionlimit(10**6)
class SegTree:
    'min'
    def __init__(self,size,default=10**15):
        self.d=default
        self.N=size
        self.v=[self.d]*(2*self.N-1)
    def update(self,i,x):
        i+=self.N-1
        self.v[i]=x
        while i>0:
            i=(i-1)//2
            self.v[i]=min(self.v[i*2+1],self.v[i*2+2])
    def min(self,a,b,i=0,l=0,r=1e9):
        if r==1e9:
            r=self.N
        if r<=a or b<=l:
            return self.d
        if a<=l and r<=b:
            return self.v[i]
        return min(self.min(a,b,i*2+1,l,(l+r)//2),self.min(a,b,i*2+2,(l+r)//2,r))
s=SegTree(2**14)
s.update(0,0)
for l,r,c in LRC:
    d2=s.min(l-1,r-1)+c
    if d2<d[r-1]:
        d[r-1]=d2
        s.update(r-1,d2)
print(-1 if d[-1]==10**15 else d[-1])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
LRC=sorted([list(map(int,input().split())) for i in range(M)])
d=[10**15]*N
d[0]=0
class SegTree:
    'min'
    def __init__(self,size,default=10**15):
        self.d=default
        self.N=size
        self.v=[self.d]*(2*self.N-1)
    def update(self,i,x):
        i+=self.N-1
        self.v[i]=x
        while i>0:
            i=(i-1)//2
            self.v[i]=min(self.v[i*2+1],self.v[i*2+2])
    def min(self,a,b,i=0,l=0,r=1e9):
        if r==1e9:
            r=self.N
        if r<=a or b<=l:
            return self.d
        if a<=l and r<=b:
            return self.v[i]
        return min(self.min(a,b,i*2+1,l,(l+r)//2),self.min(a,b,i*2+2,(l+r)//2,r))
s=SegTree(2**14)
s.update(0,0)
for l,r,c in LRC:
    d2=s.min(l-1,r-1)+c
    if d2<d[r-1]:
        d[r-1]=d2
        s.update(r-1,d2)
print(-1 if d[-1]==10**15 else d[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
import collections
import sys
N, M  = map(int, input().split(' '))
graph = np.ones((N, N), dtype=int) + 1e9
for i in range(M):
    L, R, C = map(int, input().split(' '))
    graph[L-1:R, L-1:R] = np.where(graph[L-1:R, L-1:R] > C, C, graph[L-1:R, L-1:R])
Ds = np.zeros(N, dtype=int)
for i in range(N-2, -1, -1):
    Ds[i] = (Ds[i+1:] + graph[i, i+1:]).min()
print(int(Ds[0]) if Ds[0] <= 1e9 else -1)

Submission status: Runtime Error

Solution code:
import pandas as pd
import sys

N, M = map(int, input().split())
L = []
R = []
C = []
for m in range(M):
    l,r,c = map(int, input().split())
    L.append(l)
    R.append(r)
    C.append(c)

data = pd.DataFrame({"L":L, "R":R, "C":C})
position = 1
min_c = 0
while True:
    data_tmp = data[(data["L"] <= position) & (data["R"] > position)]
    if len(data_tmp)==0:
        print(-1)
        sys.exit()
        
    min_c_tmp = data_tmp["C"].min()
    min_c += min_c_tmp
    position = data_tmp[data_tmp["C"]==min_c_tmp]["R"].max()

    if position == N:
        print(min_c)
        break

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra
import math
n,m=map(int,input().split())
edge=[[math.inf for _ in range(n)] for _ in range(n)]

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

G=csgraph_from_dense(edge,null_value=math.inf)
d=dijkstra(G,indices=0)
#print(d)
print(int(d[n-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, dtype=np.int64)
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)
if d[0, N - 1] > 10**14:
    print(-1)
else:
    print(int(d[0, N - 1]))

Submission status: Runtime Error

Solution code:
from heapq import heappop as pop
from heapq import heappush as push

INF = 10 ** 18

class edge:
  def __init__(self, to, cost):
    self.to = to
    self.cost = cost

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

G = [[] for i in range(N + 1)]
#G[i]...頂点iからの辺list、(行き先、コスト)
d = [INF for i in range(N + 1)]
#d[i]...スタートからみた頂点iまでの最短距離

def dijkstra(s):
  que = []
  d[s] = 0
  push(que, (0,s))

  while len(que):
    p = pop(que)
    v = p[1]
    if (d[v] < p[0]):
      continue
    for i in range(len(G[v])):
      e = G[v][i]
      if d[e.to] > d[v] + e.cost:
        d[e.to] = d[v] + e.cost
        push(que, (d[e.to], e.to))

for i in range(L):
  l, r, c = map(int,input().split())
  G[l-1].append(edge(r-1,c))
for i in range(L):
  G[i + 1].append(edge(i,0))
dijkstra(0)
#print(d)
if d[N-1]==1000000000000000000:
    print(-1)
else:
    print(d[N-1])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
LRC=[list(map(int,input().split())) for _ in range(n)]

dp=[float('inf')]*n
dp[0]=0
for _ in range(2):
  for i in range(m):
    l,r,c = LRC[i]
    l,r,c = l-1,r-1,c
    for j in range(r+1):
      dp[j]=min(dp[j],dp[l]+c)
if dp[-1]==float('inf'):
  print(-1)
else:
  print(dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
N, M = map(int, input().split())
g = np.full((N, N), 10 ** 10)
for i in range(M):
    l, r, c = map(int, input().split())
    g[l-1: r, l-1:r] = np.where(g[l-1: r, l-1:r] > c, c, g[l-1: r, l-1:r])
    # print(g)
g = np.where(g == 10 ** 10, 0, g)
g = g * (np.eye(N) - 1) * (-1)
ans = dijkstra(g)[0][-1]
if ans == float('INF'):
    print(-1)
else:
    print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
LRC=[list(map(int,input().split())) for _ in range(n)]

dp=[float('inf')]*n
dp[0]=0
for _ in range(2):
  for i in range(m):
    l,r,c = LRC[i]
    l,r,c = l-1,r-1,c
    for j in range(r+1):
      dp[j]=min(dp[j],dp[l]+c)
print(dp[-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections
import sortedcontainers

N,M = map(int, sys.stdin.readline().rstrip().split(" "))
pathes = collections.defaultdict(list)
for _ in range(M):
    L, R, C = map(int, sys.stdin.readline().rstrip().split(" "))
    pathes[L].append((R, C))

currents = sortedcontainers.SortedDict()
if not 1 in pathes:
    print(-1)
    exit(0)
current_minimum = 0
for n in range(1, N, 1):
    if n in pathes:
        for R, C in pathes[n]:
            if R in currents:
                currents[R] = min(currents[R], C+current_minimum)
            else:
                currents[R] = C+current_minimum
    if n == 1:
        current_minimum = currents.peekitem(0)[1]
        # current_minimum = min(currents.values())
    if n in currents:
        del currents[n]
        if len(currents) == 0:
            print(-1)
            exit(0)
        # current_minimum = min(currents.values())
        current_minimum = currents.peekitem(0)[1]
    # print(n, current_minimum, currents)


print(current_minimum)
exit(0)

Submission status: Runtime Error

Solution code:
    #D
    import math
    import numpy as np
    N, M = map(int, input().split())
    route_list = [[0 for i in range(N)] for i in range(N)]
    for i in range(M):
        L, R, C = map(int, input().split())
        for i in range(L, R):
            for j in range(i, R):
                if route_list[i-1][j] == 0:
                    route_list[i-1][j] = C
                else:
                    route_list[i-1][j] = min(route_list[i-1][j], C)
     
    node_num = len(route_list) #ノードの数
     
    unsearched_nodes = list(range(node_num)) # 未探索ノード
    distance = [np.inf] * node_num # ノードごとの距離のリスト
    previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
    distance[0] = 0 # 初期のノードの距離は0とする
     
    # @GDaigo さんのコメントより関数の追加 2017/03/18
    def get_target_min_index(min_index, distance, unsearched_nodes):
        start = 0
        while True:
            index = distance.index(min_index, start)
            found = index in unsearched_nodes
            if found:
                return index
            else:
                start = index + 1
     
    while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
        # まず未探索ノードのうちdistanceが最小のものを選択する
        posible_min_distance = np.inf # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
        for node_index in unsearched_nodes: # 未探索のノードのループ
            if posible_min_distance > distance[node_index]: 
                posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
        target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
        unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去
     
        target_edge = route_list[target_min_index] # ターゲットになるノードからのびるエッジのリスト
        for index, route_dis in enumerate(target_edge):
            if route_dis != 0:
                if distance[index] > (distance[ target_min_index] + route_dis):
                    distance[index] = distance[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                    previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新
     
    if distance[node_num - 1] is np.inf:
        print("-1")
    else:
        print(distance[node_num - 1])

Submission status: Runtime Error

Solution code:
import numpy as np
import collections
import sys
N, M  = map(int, input().split(' '))
graph = np.ones((N, N)) + 1e9
for i in range(M):
    L, R, C = map(int, input().split(' '))
    graph[L-1:R, L-1:R] = np.where(graph[L-1:R, L-1:R] > C, C, graph[L-1:R, L-1:R])
Ds = np.zeros(N)
for i in range(N-2, -1, -1):
    Ds[i] = (Ds[i+1:] + graph[i, i+1:]).min()
print(int(Ds[0]) if Ds[0] <= 1e9 else -1)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
N, M = map(int, input().split())
g = np.full((N, N), float('INF'))
for i in range(M):
    l, r, c = map(int, input().split())
    g[l-1: r, l-1:r] = np.where(g[l-1: r, l-1:r] > c, c, g[l-1: r, l-1:r])
    # print(g)
g = np.where(g == float('INF'), 0, g)
g = g * (np.eye(N) - 1) * (-1)
# print(g, shortest_path(g))
ans = dijkstra(g)[0][-1]
if ans == float('INF'):
    print(-1)
else:
    print(int(ans))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
datas=list(list(map(int,input().split())) for _ in range(M))
i1=0
i2=1
while i1!=i2:
  i1=i2
  i2=max(data[1] if data[0]<=i1 else 0 for data in datas)
if i2 != N:
  print(-1)
else:
  maximum=sum(data[2] for data in datas)
  shortest_path=list(list(maximum for _1 in range(N)) for _2 in range(N))
  for data in datas:
     for i in range(data[0],data[1],1):
         for j in range(i+1,data[1]+1,1):
             shortest_path[j][i]=min(shortest_path[j][i],data[2])

  for i in range(N-2,-1,-1):
      for j in range(i+2,N,1):
          shortest_path[j][i]=min(shortest_path[j][i],min(shortest_path[k][i]+shortest_path[j][k] for k in range(i+1,j,1)))
  print(shortest_path[N-1][0])

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop

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

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

    if r < q[0][0]:
        continue

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

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

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

# print(q)

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

print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
datas=list(list(map(int,input().split())) for _ in range(M))
i1=0
i2=1
while i1!=i2:
  i1=i2
  i2=max(data[1] if data[0]<=i1 else 0 for data in datas)
if i2 != N:
  print(-1)
else:
  maximum=sum(data[2] for data in datas)
  shortest_path=list(list(maximum for _1 in range(N)) for _2 in range(N))
  for data in datas:
     for i in range(data[0],data[1],1):
         for j in range(i+1,data[1]+1,1):
             shortest_path[j][i]=min(shortest_path[j][i],data[2]):

  for i in range(N-2,-1,-1):
      for j in range(i+2,N,1):
          shortest_path[j][i]=min(shortest_path[j][i],min(shortest_path[k][i]+shortest_path[j][k] for k in range(i+1,j,1)))
  print(shortest_path[N-1][0])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
N, M = map(int, input().split())
g = np.full((N, N), float('INF'))
for i in range(M):
    l, r, c = map(int, input().split())
    g[l-1: r, l-1:r] = np.where(g[l-1: r, l-1:r] > c, c, g[l-1: r, l-1:r])
    # print(g)
g = np.where(g == float('INF'), 0, g)
g = g * (np.eye(N) - 1) * (-1)
# print(g, shortest_path(g))
ans = shortest_path(g)[0][-1]
if ans == float('INF'):
    print(-1)
else:
    print(int(ans))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 10
for i in range(N+1):
    graph[i][i] = 0
LRC.sort(key=lambda x: x[2], reverse=True)
LRC.sort()
dp = [INF] * (N+1) # dp[0]は使わない
visited = 1
dp[1] = 0
for l, r, c in LRC:
    if l > visited:
        print(-1)
        exit()
    if r > visited:
        visited = r
    x = dp[l] + c
    dp[r] = min(dp[r], x)
if dp[N] == INF:
    print(-1)
else:
    print(dp[N])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from operator import itemgetter
from heapq import heappop, heappush
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M = inpl()
D = [0] + [10**18]*(N-1)
g0 = itemgetter(0)
Q = sorted([inpl() for _ in range(M)], key=g0, reverse=True)
#print(*Q, sep="\n")

HQ = [(0, 0)]

for i in range(N):
    while HQ[0][1] < i:
        heappop(HQ)
    v = HQ[0][0]
    while len(Q) and (i == (Q[-1][0]-1)):
        l, r, c = Q.pop()
        heappush(HQ, (v+c, r-1))


if v == 10**18:
    print(-1)
else:
    print(v)

Submission status: Runtime Error

Solution code:

N, M = map(int, input().split())
AtCodermap = [[10**10 for i in range(N)] for j in range(N)]
for i in range(M):
    L, R, C = map(int, input().split())
    AtCodermap[L-1][R-1] = C

Rootnum = N #ますめのかず
Distance = [10**10] * Rootnum #それぞれのマスまでの初期値からの距離 最初は全部無限
NotYet = [10**10]* Rootnum    #未探索の升目リスト　未探索は無限　探索済みは１になる
HowToGo = [[] for ssf in range(len(AtCodermap))]   #スタート地点からその場所への移動方法
print(Distance)
stert = 0 #スタート地点　整数で表す
Distance[stert] = 0 #初期値の場所は０

for Di in range(Rootnum):#すべてのマス探索するため
    SortedDistance = sorted(Distance)
    for Dj in range(len(AtCodermap[0])): #距離の小さいところから探索
        print(Distance)
        MASU = Distance.index(SortedDistance[Dj])
        MASUnum = MASU%len(AtCodermap[0])

        if NotYet[MASU] != 1: #きょりが小さくても探索済みなら意味がない　ここで調べるところをけってい　Djが今いるところ
            for Dk in range(len(AtCodermap[0])):#ここから探索
                print(Distance[Dk])
                if Distance[MASU] + AtCodermap[MASUnum][Dk] < Distance[Dk] and AtCodermap[MASUnum][Dk] != "A": #もし今までの距離より今いるところから行ったほうが近かったら更新
                    Distance[Dk] = AtCodermap[MASUnum][Dk] + Distance[MASU] #距離を更新

    NotYet[MASU] = 1 #調べ終わったため探索済みに変更

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