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: Wrong Answer

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

Submission status: Wrong Answer

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

import heapq
INF = 2**31-1

def dijkstra(start, edge):
    n = len(edge)
    dist = [INF]*n
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heapq.heappop(que)
        if dist[v] < d:
            continue
        for nv, nd in edge[v]:
            if dist[nv] > d + nd:
                dist[nv] = d + nd
                heapq.heappush(que, (dist[nv], nv))
    return dist
  
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(1, n):
  G[i].append((i-1, 0))
for _ in range(m):
  l, r, c = map(int, input().split())
  G[l-1].append((r-1, c))

D = dijkstra(0, G)
ans = D[n-1]
if ans == INF:
  ans = -1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def main():
    N,M = map(int,input().split())
    INF = 10**10+1
    root = [[] for _ in range(N)]
    for i in range(N-1):
        root[i+1].append((0,i))
    for _ in range(M):
        l,r,c = map(int,input().split())
        root[l-1].append((c,r-1))
    
    dist = [INF for _ in range(N)]
    q = [(0,0)]
    dist[0] = 0
    while q:
        d,now = heapq.heappop(q)
        if dist[now] < d:
            continue
        for cost,fol in root[now]:
            _d = d+cost
            if dist[fol] > _d:
                dist[fol] = _d
                heapq.heappush(q,(_d,fol))

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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_d = np.array([input().split() for _ in range(M)], dtype=np.int64)
edge_n = np.vstack([np.arange(2, N + 1, dtype=np.int64),
                   np.arange(1, N, dtype=np.int64),
                   np.ones(N - 1, dtype=np.int64)]).T
edge = np.concatenate([edge_d, edge_d[:, [1, 0, 2]], edge_n]).T

matr = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
ans = dijkstra(matr, indices=0)[-1]
if ans == np.inf:
    ans = 0
print(int(ans) - 1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq
def main():
    N, M = map( int, input().split())
    d = dict()
    E = [[] for _ in range(N)]
    for i in range(N-1):
        E[i+1].append(i)
        d[(i+1,i)] = 0
    for _ in range(M):
        l, r, c = map( int, input().split())
        l -= 1
        r -= 1
        E[l].append(r)
        d[(l,r)] = c
    q = [(0,0)]
    heapq.heapify(q)
    path = [10**17]*N
    path[0] = 0
    while q:
        c, v = heapq.heappop(q)
        for e in E[v]:
            if path[e] > c + d[(v,e)]:
                path[e] = c + d[(v,e)]
                heapq.heappush(q, (path[e], e))
    if path[N-1] == 10**17:
        print(-1)
    else:
        print(path[N-1])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq
def main():
    N, M = map( int, input().split())
    d = dict()
    E = [[] for _ in range(N)]
    for i in range(N-1):
        E[i+1].append(i)
        d[(i+1,i)] = 0
    for _ in range(M):
        l, r, c = map( int, input().split())
        l -= 1
        r -= 1
        E[l].append(r)
        d[(l,r)] = c
    q = [(0,0)]
    heapq.heapify(q)
    path = [10**17]*N
    path[0] = 0
    while q:
        c, v = heapq.heappop(q)
        for e in E[v]:
            if path[e] > path[v] + d[(v,e)]:
                path[e] = path[v] + d[(v,e)]
                heapq.heappush(q, (path[e], e))
    if path[N-1] == 10**17:
        print(-1)
    else:
        print(path[N-1])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq
def main():
    N, M = map( int, input().split())
    d = dict()
    E = [[] for _ in range(N)]
    for i in range(N-1):
        E[i+1].append(i)
        d[(i+1,i)] = 0
    for _ in range(M):
        l, r, c = map( int, input().split())
        l -= 1
        r -= 1
        E[l].append(r)
        d[(l,r)] = c
    q = [(0,0)]
    heapq.heapify(q)
    path = [10**17]*N
    path[0] = 0
    while q:
        c, v = heapq.heappop(q)
        for e in E[v]:
            if path[e] > path[v] + d[(v,e)]:
                path[e] = path[v] + d[(v,e)]
                heapq.heappush(q, (path[e], e))
    if path[N-1] == 10**15:
        print(-1)
    else:
        print(path[N-1])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq
def main():
    N, M = map( int, input().split())
    d = dict()
    E = [[] for _ in range(N)]
    for i in range(N-1):
        E[i+1].append(i)
        d[(i+1,i)] = 0
    for _ in range(M):
        l, r, c = map( int, input().split())
        l -= 1
        r -= 1
        E[l].append(r)
        d[(l,r)] = c
    q = [(0,0)]
    heapq.heapify(q)
    path = [10**15]*N
    path[0] = 0
    while q:
        c, v = heapq.heappop(q)
        for e in E[v]:
            if path[e] > path[v] + d[(v,e)]:
                path[e] = path[v] + d[(v,e)]
                heapq.heappush(q, (path[e], e))
    if path[N-1] == 10**15:
        print(-1)
    else:
        print(path[N-1])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq
def main():
    N, M = map( int, input().split())
    d = dict()
    E = [[] for _ in range(N)]
    for i in range(N-1):
        E[i+1].append(i)
        d[(i+1,i)] = 0
    for _ in range(M):
        l, r, c = map( int, input().split())
        l -= 1
        r -= 1
        E[l].append(r)
        d[(l,r)] = c
    q = [(0,0)]
    heapq.heapify(q)
    path = [-1]*N
        
    while q:
        c, v = heapq.heappop(q)
        if path[v] != -1:
            continue
        path[v] = c
        for e in E[v]:
            if path[e] == -1:
                heapq.heappush(q, (c+d[(v,e)], e))
    print(path[N-1])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq
def main():
    N, M = map( int, input().split())
    d = dict()
    E = [[] for _ in range(N)]
    for i in range(N-1):
        E[i+1].append(i)
        d[(i+1,i)] = 0
    for _ in range(M):
        l, r, c = map( int, input().split())
        l -= 1
        r -= 1
        E[l].append(r)
        d[(l,r)] = c
    q = [(0,0)]
    heapq.heapify(q)
    path = [-1]*N
    while q:
        c, v = heapq.heappop(q)
        if path[v] >= 0:
            continue
        path[v] = c
        for e in E[v]:
            if path[e] == -1:
                heapq.heappush(q, (c+d[(v,e)], e))
    print(path[N-1])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
def main():
    N, M = map( int, input().split())
    d = dict()
    E = [[] for _ in range(N)]
    for i in range(N-1):
        E[i+1].append(i)
        d[(i+1,i)] = 0
    for _ in range(M):
        l, r, c = map( int, input().split())
        l -= 1
        r -= 1
        E[l].append(r)
        d[(l,r)] = c
    q = [(0,0)]
    path = [-1]*N
    while q:
        c, v = heapq.heappop(q)
        if path[v] >= 0:
            continue
        path[v] = c
        for e in E[v]:
            if path[e] == -1:
                heapq.heappush(q, (c+d[(v,e)], e))
    print(path[N-1])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

class Dijkstra:
    # heapqのimportを忘れずに

    def __init__(self, edge, start_point, goal_point=None):
        self.edge = edge
        self.start_point = start_point
        self.goal_point = goal_point

    def get_path(self, goal, prev):
        # ゴールまでの最短経路を求める
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

    def execute(self):
        num_of_edge = len(self.edge)
        dist = [float("inf") for _ in range(num_of_edge)]
        prev = [float("inf") for _ in range(num_of_edge)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))

        while len(heap_q) > 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.edge[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src

        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

n,m = map(int,input().split())
data = [{} for _ in range(n)]
for i in range(1,n):
    data[i][i-1] = 0

for i in range(m):
    l,r,c = map(int,input().split())
    l -= 1
    r -= 1
    data[l][r] = c
    data[r][l] = c
#print(data)
dk =Dijkstra(data,0)
ans = dk.execute()

print(-1 if ans[n-1] == float("inf") else ans[n-1])

Submission status: Wrong Answer

Solution code:
import heapq

class Dijkstra:
    # heapqのimportを忘れずに

    def __init__(self, edge, start_point, goal_point=None):
        self.edge = edge
        self.start_point = start_point
        self.goal_point = goal_point

    def get_path(self, goal, prev):
        # ゴールまでの最短経路を求める
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

    def execute(self):
        num_of_edge = len(self.edge)
        dist = [float("inf") for _ in range(num_of_edge)]
        prev = [float("inf") for _ in range(num_of_edge)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))

        while len(heap_q) > 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.edge[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src

        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

n,m = map(int,input().split())
data = [{} for _ in range(n)]
for i in range(1,n):
    data[i][i-1] = 0

for i in range(m):
    l,r,c = map(int,input().split())
    l -= 1
    r -= 1
    data[l][r] = c
    data[r][l] = c
#print(data)
dk =Dijkstra(data,0)
ans = dk.execute()

print(ans[n-1] if ans[n-1] < float("inf") else -1)

Submission status: Wrong Answer

Solution code:
import heapq

class Dijkstra:
    # heapqのimportを忘れずに

    def __init__(self, edge, start_point, goal_point=None):
        self.edge = edge
        self.start_point = start_point
        self.goal_point = goal_point

    def get_path(self, goal, prev):
        # ゴールまでの最短経路を求める
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

    def execute(self):
        num_of_edge = len(self.edge)
        dist = [float("inf") for _ in range(num_of_edge)]
        prev = [float("inf") for _ in range(num_of_edge)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))

        while len(heap_q) > 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.edge[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src

        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

n,m = map(int,input().split())
data = [{} for _ in range(n)]
for i in range(1,n):
    data[i][i-1] = 0

for i in range(m):
    l,r,c = map(int,input().split())
    l -= 1
    r -= 1
    data[l][r] = c
#print(data)
dk =Dijkstra(data,0)
ans = dk.execute()

print(ans[n-1] if ans[n-1] < float("inf") else -1)

Submission status: Wrong Answer

Solution code:
import heapq

class Dijkstra:
    # heapqのimportを忘れずに

    def __init__(self, edge, start_point, goal_point=None):
        self.edge = edge
        self.start_point = start_point
        self.goal_point = goal_point

    def get_path(self, goal, prev):
        # ゴールまでの最短経路を求める
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

    def execute(self):
        num_of_edge = len(self.edge)
        dist = [float("inf") for _ in range(num_of_edge)]
        prev = [float("inf") for _ in range(num_of_edge)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))

        while len(heap_q) > 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.edge[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src

        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

n,m = map(int,input().split())
data = [{} for _ in range(n)]
for i in range(1,n):
    data[i][i-1] = 0

for i in range(m):
    l,r,c = map(int,input().split())
    l -= 1
    r -= 1
    data[l][r] = c
#print(data)
dk =Dijkstra(data,0)
ans = dk.execute()

print(ans[n-1])

Submission status: Wrong Answer

Solution code:
INF = 10 ** 9

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

G = [[] for _ in range(N + 1)]
for _ in range(M):
    L, R, C = map(int, input().split())
    G[L].append([C, R])
    G[R].append([C, L])

for i in range(1, N):
    G[i + 1].append([0, i])

d = [INF] * (N + 1)

def dijkstra(s):
    import heapq
    d[s] = 0
    pque = []
    heapq.heappush(pque, [0, s])
    
    while pque:
        p = heapq.heappop(pque)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[1]] > d[v] + e[0]:
                d[e[1]] = d[v] + e[0]
                heapq.heappush(pque, [d[e[1]], e[1]])

dijkstra(1)

print (-1 if d[-1] == INF else d[-1])

Submission status: Wrong Answer

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

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

E = np.asarray(edges)
fr, to, w = E[:, 0], E[:, 1], E[:, 2]
graph = csr_matrix((w, (fr, to)), shape=(N, N), dtype=np.int64)
dists = dijkstra(graph, indices=0)

if np.isinf(dists[-1]):
    print(-1)
else:
    print(int(dists[-1]))

Submission status: Wrong Answer

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

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

E = np.asarray(edges)
fr, to, w = E[:, 0], E[:, 1], E[:, 2]
graph = csr_matrix((w, (fr, to)), shape=(N, N))
dists = dijkstra(graph, indices=0)

if np.isinf(dists[-1]):
    print(-1)
else:
    print(int(dists[-1]))

Submission status: Wrong Answer

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)
    if d[n-1] == np.inf:
        print(-1)
    else:
        print(int(d[n-1]))


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 1 << 32
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    l, r, c = LI()
    G[l - 1] += [(r - 1, c)]


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


def dijkstra(G, s=0):
    hq = [(0, s)]
    dist = [INF] * n
    dist[s] = 0
    checked = [0] * n
    while hq:
        min_dist, u = heappop(hq)
        if checked[u]:
            continue
        checked[u] = 1
        for v, c in G[u]:
            if checked[v]:
                continue
            elif dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                heappush(hq, (dist[u] + c, v))
    return dist


ans = dijkstra(G)[-1]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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 t
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: Wrong Answer

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 t
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: Wrong Answer

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 t
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(s[n+a-2])

Submission status: Wrong Answer

Solution code:
def func(x,y):
    return min(x,y)

class SegmentTree:
    def __init__(self, n): #a1, a2, ..., an
        n_ = 1
        while n_ < n:
            n_ *= 2

        self.n = n_
        self.arr = [float("inf")] * (2*self.n-1)

    def update(self, k, a): #0_indexed
        k += self.n - 1
        self.arr[k] = a

        while k > 0:
            k = (k-1) // 2
            self.arr[k] = min(self.arr[2*k+1], self.arr[2*k+2])

    def query(self, l, r):
        L, R = l+self.n, r+self.n
        ide_ele = float("inf")
        #単位元(ide_ele)は、区間外の値などに設定する値です。
         #ex) 最小値のセグ木 → +inf
         #　和のセグ木 → 0
         #　積のセグ木 → 1
         #  gcdのセグ木 → 0
        res = ide_ele
        while L < R:
            if R & 1:
                R -= 1
                res = func(res, self.arr[R-1]) #

            if L & 1:
                res = func(res, self.arr[L-1])
                L += 1

            L >>= 1
            R >>= 1

        return res


import sys
input=sys.stdin.readline
n,m=map(int,input().split())

sg=SegmentTree(n+1)
sg.update(1,0)

for _ in range(m):
    l,r,c=map(int,input().split())
    x=sg.query(l,l+1)
    if x!=float("inf"):
        x+=c
        for i in range(l,r+1):
            sg.update(i,min(x,sg.query(i,i+1)))

print(sg.query(n,n+1) if sg.query(n,n+1)!=float("inf") else -1)

Submission status: Wrong Answer

Solution code:
import heapq

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

inf = 1 << 60
dp = [0] + [inf] * (n - 1)
queue = [(0, 0)]
check = [False] * n
while queue:
  dist, act = heapq.heappop(queue)
  check[act] = True
  for cost, vertex in edge[act]:
    if check[vertex]:
      continue
    d = dist + cost
    if dp[vertex] > dist:
      heapq.heappush(queue, (d, vertex))
      dp[vertex] = d
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import heapq

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

inf = 1 << 60
dp = [0] + [inf] * (n - 1)
queue = [(0, 0)]
check = [False] * n
while queue:
  dist, act = heapq.heappop(queue)
  check[act] = True
  for cost, vertex in edge[act]:
    if check[vertex]:
      continue
    d = dist + cost
    if dp[vertex] > dist:
      heapq.heappush(queue, (d, vertex))
      dp[vertex] = d
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
inf = 10.0 ** 10
path_data = []
for i in range(m):
    path_data.append(list(map(int, input().split())))
path_data.sort()
dp = [inf] * (n + 1)
dp[0] = 0
dp[1] = 0
for i in range(m):
    l = path_data[i][0]
    r = path_data[i][1]
    c = path_data[i][2]
    if dp[l] == inf:
        continue
    for j in range(l, r+1):
        dp[j] = min(dp[j], dp[l] + c)
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
lines = readlines()
edge = np.array([line.split() for line in lines], dtype = np.int64)
edge = sorted(edge,key=lambda x:(x[0],x[1],x[2]))

for i in range(1,M):
  if edge[i][0] == edge[i-1][0] and edge[i][1] == edge[i-1][1]:
    edge[i][2] = edge[i-1][2]
#print(edge)
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
edge = np.concatenate([X,edge]).T
graph = csr_matrix((edge[2], (edge[: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: Wrong Answer

Solution code:
import heapq
INF=10**9
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
d=[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]!=INF else -1)

Submission status: Wrong Answer

Solution code:
import heapq
 
def dijkstras(graph):
    cost = [10 ** 9 for _ in range(len(graph))]
    start = 0
    cost[start] = 0
    queue = [(cost[start], start)]
    while queue:
        edge_from_cost, edge_from = heapq.heappop(queue)
        if cost[edge_from] < edge_from_cost: continue
        for edge_to, edge_to_cost in graph[edge_from]:
            if cost[edge_to] > edge_from_cost + edge_to_cost:
                cost[edge_to] = cost[edge_from] + edge_to_cost
                heapq.heappush(queue, (cost[edge_to], edge_to))
 
    return cost
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
reverse_graph = [[] for _ in range(m)]
for i in range(m):
    l, r, c = map(int, input().split())
    l -= 1
    r -= 1
    graph[l].append((r, c))
    for j in range(l+1,r+1):
        graph[r].append((j,0)) 
ans = dijkstras(graph)[n-1]
if ans == 10 **9:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
 
def dijkstras(graph):
    cost = [10 ** 9 for _ in range(len(graph))]
    start = 0
    cost[start] = 0
    queue = [(cost[start], start)]
    while queue:
        edge_from_cost, edge_from = heapq.heappop(queue)
        if cost[edge_from] < edge_from_cost: continue
        for edge_to, edge_to_cost in graph[edge_from]:
            if cost[edge_to] > edge_from_cost + edge_to_cost:
                cost[edge_to] = cost[edge_from] + edge_to_cost
                heapq.heappush(queue, (cost[edge_to], edge_to))
 
    return cost
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
reverse_graph = [[] for _ in range(m)]
for i in range(m):
    l, r, c = map(int, input().split())
    l -= 1
    r -= 1
    graph[l].append((r, c))
    for j in range(l+1,r+1):
        graph[r].append((j,0))
print(dijkstras(graph)[n-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

N, M = inpl()
q = []
LRC = sorted([inpl() for _ in range(M)])
points = sorted(list({lrc[i] for i in range(2) for lrc in LRC}))
positions = dict()
P = 0
prev = -1
for p in points:
    if p > prev:
        prev = p
        positions[p] = P
        P += 1
m = 0
dq = [(0,0)]
for i in range(P):
    while dq and dq[0][1] < i:
        heappop(dq)
    if not dq:
        print(-1)
        break
    d = dq[0][0]
    while m < M and positions[LRC[m][0]] == i:
        heappush(dq, (d+LRC[m][2], positions[LRC[m][1]]))
        m += 1
else:
    print(d)