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:
def main():
    from sys import stdin
    input = stdin.readline

    import numpy as np
    n, m = map(int, input().split())
    abc = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[u-1].append([v-1, c]) for u, v, c in abc]
    [g[i+1].append([i, 0]) for i in range(n-1)]

    import heapq

    yen = np.full(n, np.inf)
    h = [(0, 0)]
    heapq.heapify(h)
    while h:
        d, i = heapq.heappop(h)
        if yen[i] == np.inf:
            yen[i] = d
            for x, y in g[i]:
                heapq.heappush(h, (d+y, x))
    print(int(yen[n-1]))


main()

Submission status: Runtime Error

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    import scipy.sparse as sp
    n, m = map(int, input().split())
    abc = np.array([list(map(int, input().split())) for _ in [0]*m])
    data = np.append(abc[:, 2], np.zeros(n-1))
    row = np.append(abc[:, 0]-1, np.arange(1, n))
    col = np.append(abc[:, 1]-1, np.arange(n-1))
    matrix = sp.csr_matrix((data, (row, col)), shape=(n, n), dtype=np.int32)
    d = sp.csgraph.dijkstra(matrix, indices=0)
    print(int(d[n-1]))


main()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
p=sorted([list(map(int,input().split()))for i in range(m)])
a=2**(n).bit_length()
b=2**31-1
s=[b]*(2*a)
def f(k,x):
    k+=a-1
    s[k]=x
    while k>=0:
        k=(k-1)//2
        s[k]=min(s[2*k+1],s[2*k+2])
def g(l,r):
    L,R=l+a,r+a
    t=b
    while L<R:
        if R&1:
            R-=1
            t=min(t,s[R-1])
        if L&1:
            t=min(t,s[L-1])
            L+=1
        L>>=1
        R>>=1
    return s
f(0,0)
for l,r,c in p:
    q=g(l-1,r-1)
    if s[r+a-2]>q+c
        f(r-1,c+q)
print(-1 if s[n+a-2]==b else s[n+a-2])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
p=sorted([list(map(int,input().split()))for i in range(m)])
a=2**(n-1).bit_length()
b=2**31-1
s=[b]*(2*a)
def f(k,x):
    k+=a-1
    s[k]=x
    while k>=0:
        k=(k-1)//2
        s[k]=min(s[2*k+1],s[2*k+2])
def g(l,r):
    L,R=l+a,r+a
    t=b
    while L<R:
        if R&1:
            R-=1
            t=min(t,s[R-1])
        if L&1:
            t=min(t,s[L-1])
            L+=1
        L>>=1
        R>>=1
    return s
f(0,0)
for l,r,c in p:
    q=g(l-1,r-1)
    if s[r+a-2]>q+c
        f(r-1,c+q)
print(-1 if s[n+a-2]==b else s[n+a-2])

Submission status: Runtime Error

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
X=sorted([(A[i],B[i]) for i in range(N)],key=lambda x:x[1])
A=[X[i][0] for i in range(N)]
B=[X[i][1] for i in range(N)]
C=sorted([(A[i],i) for i in range(N)],key=lambda x:x[0])
for i in range(N):
    if C[i][0]>B[i]:
        print("No")
        exit()
if len(set(A))<N:
    print("Yes")
    exit()
Y=[0 for i in range(N)]
j=0
for i in range(N):
    Y[j]=1
    j=C[j][1]
    
if sum(Y)==N:
    #A:C[i][0]
    #B:X[i][1]
    for i in range(N-1):
        if C[i+1][0]<=X[i][1]:
            print("Yes")
            exit()
    print("No")
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
/*
　　　∫ ∫ ∫
　　　ノヽ
　　（＿　 ）
　（＿　　　 ）
（＿＿＿＿＿＿ ）
　ヽ(´･ω･)ﾉ　
　　 |　 /
　　 UU
*/
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
using P = pair<ll, ll>;
typedef vector<int> vi;
const int MOD = (int)1e9 + 7;
const ll INF = 1LL << 62;
const int inf = 1<<30;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = s; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end() //コンテナじゃないと使えない!!
#define debug(x) cerr << #x << ": " << x << "\n";
#define mp make_pair
template <typename T>
ostream& operator<<(ostream& os, vector<T> &V){
    int N = V.size();
    REP(i,N){
        os << V[i];
        if (i!=N-1) os << " ";
    }
    os << "\n";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, pair<T,T> const&P){
    os << P.first;
    os << " ";
    os << P.second;
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, set<T> &S){
    auto it=S.begin();
    while(it!=S.end()){
        os << *it;
        os << " ";
        it++;
    }
    os << "\n";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, deque<T> &q){
    for(auto it=q.begin();it<q.end();it++){
        os<<*it;
        os<<" ";
    }
     os<<endl;
    return os;
}
vector<pair<int,int>> dxdy = {mp(0,1),mp(1,0),mp(-1,0),mp(0,-1)};
//fixed<<setprecision(10)<<ans<<endl;


template <typename T>
struct SegmentTree{
    /*
    ~~~~1-indexで実装~~~~
            1
        2       3
      4   3   5    6

    ~~~~親・兄弟・子へのアクセスの仕方~~~~
                i<<1
            i           i^1
    i<<1|0   i<<1|1
    */


    using F = function<T(T,T)>;
    int N;
    F func; //関数(minとか)
    T identity; //単位元
    vector<T> data; //上から添字 2*Nくらいのノード
    SegmentTree(){}
    SegmentTree(F f,T identity):func(f),identity(identity){}

    void init(int n_){
        N=1;
        while(N<n_) N<<=1; //完全二分木がいいので2^k個にする
        data.assign(N<<1, identity); //2N個のノード
    }

    //木を構成(vectorを元に各ノードの値を計算)
    void build(const vector<T>& v){
        int n_ = v.size();
        init(n_);
        for(int i=0; i<n_; i++){
            data[N+i] = v[i]; //葉
        }
        for(int i=n_-1; i; i++){
            data[i] = func(data[i<<1], data[(i<<1)+1] ); //子をみて親を更新
        }
    }

    //k番目の値をxに変える
    void set_val(int k, T x){
        k+=N; //indexをセグ木でのindexに変換
        data[k] = x; //値の書き換え(葉)
        while(k>>=1){ //右シフトして0にならない間
            data[k] = func(data[k<<1], data[(k<<1)+1] );
        }
    }

    //https://hcpc-hokudai.github.io/archive/structure_segtree_001.pdf
    //閉開区間[left,right)で
    T query(int left,int right){
        T left_val=identity, right_val=identity; 
        for(int l=left+N,r=right+N; l<r; l>>=1,r>>=1){
            if(l&1) left_val = func(left_val, data[l++] );
            if(r&1) right_val = func(data[--r], right_val);
        }
        return func(left_val, right_val);
    }

    //葉の値を取得する
    T get_val(int idx){
        return data[idx+N];
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M;
    cin >> N >> M;


    SegmentTree<int> S(
        [](int a,int b)->int{
            return min(a,b);
        }, __INT_MAX__
    );

    S.init(N);
    S.set_val(0,0);

    vector<tuple<int,int,int>> query;
    int l,r,c;
    REP(i,M){
        cin>>l>>r>>c;
        l--;r--;
        query.emplace_back(l,r,c);
    }

    sort(ALL(query));
    REP(i,M){
        tie(l,r,c) = query[i];
        auto from = S.query(l,r);
        if(from==S.identity){
            cout << "-1\n";
            return 0;
        }
        auto to = S.query(r,r+1);
        if(to>from+c) S.set_val(r,from+c);
    }

    int ans = S.get_val(N-1);
    cout << ans << endl;
}















/*
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
using P = pair<ll, ll>;
typedef vector<int> vi;
const int MOD = (int)1e9 + 7;
const ll INF = 1LL << 60;
const int inf = 1<<30;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = s; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end() //コンテナじゃないと使えない!!
#define debug(x) cerr << #x << ": " << x << "\n";
#define mp make_pair
template <typename T>
ostream& operator<<(ostream& os, vector<T> &V){
    int N = V.size();
    REP(i,N){
        os << V[i];
        if (i!=N-1) os << " ";
    }
    os << "\n";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, pair<T,T> const&P){
    os << P.first;
    os << " ";
    os << P.second;
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, set<T> &S){
    auto it=S.begin();
    while(it!=S.end()){
        os << *it;
        os << " ";
        it++;
    }
    os << "\n";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, deque<T> &q){
    for(auto it=q.begin();it<q.end();it++){
        os<<*it;
        os<<" ";
    }
     os<<endl;
    return os;
}
vector<ll> dijkstra(vector<vector<pair<ll,ll>>> const& edge, ll start){
    ll N = edge.size();
    vector<ll> dist(N,INF);
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll>> > q;
    q.push(mp(0, start));
    vector<bool> visited(N,false);
    
    ll from,d;
    ll to,cost;
    while(!q.empty()){
        tie(d,from) = q.top(); q.pop();
        if (visited[from]) continue;
        visited[from] = true;
        dist[from] = d;
        for(auto e:edge[from]){
            tie(to,cost) = e;
            if (visited[to]) continue;
            q.push(mp(d+cost, to));
        }
    }

    return dist;
}
//fixed<<setprecision(10)<<ans<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M;
    cin >> N >> M;
    vector<vector<pair<ll,ll>>> edge(N);
    int l,r,c;
    REP(i,M){
        cin >> l >> r >> c;
        l--;r--;
        edge[l].push_back(mp(r,c)); 
    }
    REP(i,N-1) edge[i+1].push_back(mp(i,0)); //重み0の辺
    auto dist = dijkstra(edge, 0);

    if (dist[N-1]>=INF) cout << -1 << endl;
    else cout << dist[N-1]<< endl;
}
*/

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
import sys
sys.setrecursionlimit(200000)
inf = (2.0) ** (62-1)
n, m = list(map(int, input().split()))
#infを初期化
graph = np.full((n+1,n+1), inf)
#重み0の辺を追加(0にすると、辺が存在しないことになるため、小さい数を代入)
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 = shortest_path(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
import sys
sys.setrecursionlimit(200000)
inf = (2) ** (62-1)
n, m = list(map(int, input().split()))
#infを初期化
graph = np.full((n+1,n+1), inf)
#重み0の辺を追加(0にすると、辺が存在しないことになるため、小さい数を代入)
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
import sys
sys.setrecursionlimit(200000)
inf = (2.0) ** (62-1)
n, m = list(map(int, input().split()))
#infを初期化
graph = np.full((n+1,n+1), inf)
#重み0の辺を追加(0にすると、辺が存在しないことになるため、小さい数を代入)
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 = (2.0) ** (62-1)
n, m = list(map(int, input().split()))
#infを初期化
graph = np.full((n+1,n+1), inf)
#重み0の辺を追加(0にすると、辺が存在しないことになるため、小さい数を代入)
for i in range(1,n+1):
    graph[i][i - 1] = 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 = (2.0) ** (62-1)
n, m = list(map(int, input().split()))
#infを初期化
graph = np.full((n+1,n+1), inf)
#重み0の辺を追加(0にすると、辺が存在しないことになるため、小さい数を代入)
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 import csr_matrix
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
edge = np.array([input().split() for _ in range(M)], dtype = np.int64)
edge = sorted(edge,key=lambda x:(x[0],x[1],x[2]))

edge2 = np.array(edge[0])
for i in range(1,M):
  if edge[i][0] == edge[i-1][0] and edge[i][1] == edge[i-1][1]:
    continue
  edge2 = np.vstack([edge2,edge[i]])

x = np.arange(N,1,-1)
y = np.arange(N-1,0,-1)
z = np.zeros(N-1,int)
X = np.vstack([x,y,z]).T
edge2 = np.concatenate([X,edge2]).T
graph = csr_matrix((edge2[2], (edge2[:2] - 1)), (N, N))
distance_mat = dijkstra(graph, directed = True, indices = 0)
#print(distance_mat)
print(-1 if distance_mat[-1] == float("inf") else int(distance_mat[-1]))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra, shortest_path, csgraph_from_dense
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())
g = np.full((n, n), np.inf)

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

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

Submission status: Runtime Error

Solution code:
import math
import heapq
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
d=[math.inf for _ in range(n)]
d[0]=0

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

q=[]
heapq.heapify(q)
heapq.heappush(q, [0,0])

def dijkstra():
    while(len(q)!=0):
        cs=heapq.heappop(q)
        cost=cs[0]
        start=cs[1]

        if(d[start] < cost):
            continue

        e=edge[start]
        for ei in e:
            if(d[ei[1]] > d[start]+ei[0]):
                heapq.heappush(q, [d[start]+ei[0],ei[1]])
                d[ei[1]] = d[start]+ei[0]

dijkstra()
print(d[len(d)-1] if d[len(d)-1]!=math.inf else -1)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra, shortest_path, csgraph_from_dense
import numpy as np
 
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 8)
 
 
n, m = map(int,readline().split())
 
inf = float("inf")
 
g = np.full((n, n), inf)
 
for i in range(m):
    l, r, c = map(int,readline().split())
    g[l-1, r-1] = np.minimum(g[l-1, r-1], c)
    #g[r-1, l-1:r-1] = 0
    for i in range(r-l):
        g[r-1-i, r-2-i] = 0
g = csgraph_from_dense(g, null_value=inf)
 
ans = dijkstra(g, indices = 0)[n-1]
if ans > 10**14:
	print(-1)
else:
	print(int(ans))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra, shortest_path, csgraph_from_dense
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 = float("inf")

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

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

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

Submission status: Runtime Error

Solution code:
# 抽象化をやめた場合
class Rmq(object):
    __slots__ = ["elem_size", "tree", "real_size"]

    def __init__(self, a):
        if hasattr(a, "__iter__"):
            self.real_size = len(a)
            self.elem_size = elem_size = 1 << (self.real_size-1).bit_length()
            self.tree = tree = [float("inf")] * (elem_size * 2)
            tree[elem_size:elem_size + self.real_size] = a
            for i in range(elem_size - 1, 0, -1):
                tree[i] = min(tree[i << 1], tree[(i << 1) + 1])
        elif isinstance(a, int):
            self.real_size = a
            self.elem_size = elem_size = 1 << (self.real_size-1).bit_length()
            self.tree = [float("inf")] * (elem_size * 2)

    def get_value(self, x: int, y: int) -> int:  # 半開区間
        l, r = x + self.elem_size, y + self.elem_size
        tree = self.tree
        result = float("inf")
        while l < r:
            if l & 1:
                result = min(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = min(tree[r], result)
            l, r = l >> 1, r >> 1
        return result

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        tree = self.tree
        tree[k] = value
        while k > 1:
            k >>= 1
            tree[k] = min(tree[k << 1], tree[(k << 1) + 1])

    def get_one_value(self, i):
        return self.tree[i+self.elem_size]

    def debug(self):
        print(self.tree[self.elem_size:self.elem_size+self.real_size])


from operator import itemgetter

N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
LRC.sort(key=itemgetter(0))

idx_LRC = 0
q = []

seg = SegmentTree(N+1, float("inf"), min)

seg.set_value(1, 0)
for v in range(1, N + 1):
    d = seg.get_value(v, N + 1)
    while idx_LRC < M:
        l, r, c = LRC[idx_LRC]
        if l <= v:
            seg.set_value(r, min(seg.tree[r + seg.elem_size], d + c))
            idx_LRC += 1
        else:
            break
ans = seg.tree[N + seg.elem_size]
print(ans if ans != float("inf") else -1)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
inf = (2.0) ** (62-1)
n, m = list(map(int, input().split()))
#infを初期化
graph = np.full((n+1,n+1), inf)
#重み0の辺を追加(0にすると、辺が存在しないことになるため、小さい数を代入)
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()))
#infを初期化
graph = np.full((n+1,n+1), inf)
#重み0の辺を追加(0にすると、辺が存在しないことになるため、小さい数を代入)
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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s):
    prev = {}
    q = []
    d = defaultdict(lambda: INF)
    d[s] = 0
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if d[u] < c:
            continue
        for v in g[u]:
            alt = g[u][v] + c
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (alt, v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)

    for l, r, c in LRC:
        g[l][r] = c
    
    for i in range(1, N):
        g[i+1][i] = 0

    
    d = Dijkstra(g, 1, N)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 10.0**100


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s, N):
    V = set(range(1, N+1))

    d = {}
    prev = {}
    q = []
    done = set()
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = INF
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)
    for i in range(1, N):
        g[i+1][i] = 0

    for l, r, c in LRC:
        g[l][r] = c
        if g[r][l] != 0:
            g[r][l] = c
    
    d = Dijkstra(g, 1, N)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = set(V)

    d = {}
    prev = {}
    q = []
    done = set()
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = INF
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)
    for i in range(2, N+1):
        g[i+1][i] = 0

    for l, r, c in LRC:
        g[l][r] = c
        g[r][l] = c
    
    d = Dijkstra(g, 1)

    return -1 if d[N] == INF else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Dijkstra(g, s):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = set(V)

    d = {}
    prev = {}
    q = []
    done = set()
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = INF
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d


@mt
def slv(N, LRC):
    g = defaultdict(dict)
    for i in range(2, N+1):
        g[i+1][i] = 0

    for l, r, c in LRC:
        g[l][r] = c
        g[r][l] = c
    
    d = Dijkstra(g, 1)

    return -1 if N not in d else d[N]


def main():
    N, M = read_int_n()
    LRC = [read_int_n() for _ in range(M)]
    print(slv(N, LRC))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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