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:
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, 0))

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

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):
    for t in range(l,r+1):
      if s != t:
        if Glaph[s][t] == 0 or Glaph[s][t] > c:
          Glaph[s][t] = 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: Wrong Answer

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
V = [[] for _ in range(N)]
for i in range(1,N):
    V[i].append((i-1, 0))
for _ in range(M):
    l, r, c = map(int, input().split())
    V[l-1].append((r-1, c))
INF = float('inf')

q = [(0, 0)]
d = [INF] * N
d[0] = 0

while q:
    _, u = heappop(q)
    for v, c in V[u]:
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(q, (d[v], v))

print(d[-1])

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10**10
N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

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

S = 0

def dijkstra(N, S):
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] # ノード
        dis = q[0] # 過去に更新された最短距離

        # vまで2番目に短い距離（最新）　＜　過去最短距離　の時、
        # キューから取り出した過去のものを無視する
        if d[ver] < dis:
            continue

        # 隣接リストに対してループ
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

ans = dijkstra(N, S)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10**11
N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

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

S = 0

def dijkstra(N, S):
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] # ノード
        dis = q[0] # 過去に更新された最短距離

        # vまで2番目に短い距離（最新）　＜　過去最短距離　の時、
        # キューから取り出した過去のものを無視する
        if d[ver] < dis:
            continue

        # 隣接リストに対してループ
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

ans = dijkstra(N, S)
if ans == INF:
    print(-1)
else:
    print(dijkstra(N, S))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10**10
N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

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

S = 0

def dijkstra(N, S):
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] # ノード
        dis = q[0] # 過去に更新された最短距離

        # vまで2番目に短い距離（最新）　＜　過去最短距離　の時、
        # キューから取り出した過去のものを無視する
        if d[ver] < dis:
            continue

        # 隣接リストに対してループ
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

ans = dijkstra(N, S)
if ans == INF:
    print(-1)
else:
    print(dijkstra(N, S))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10**13
N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

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

S = 0

def dijkstra(N, S):
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] # ノード
        dis = q[0] # 過去に更新された最短距離

        # vまで2番目に短い距離（最新）　＜　過去最短距離　の時、
        # キューから取り出した過去のものを無視する
        if d[ver] < dis:
            continue

        # 隣接リストに対してループ
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

ans = dijkstra(N, S)
if ans == INF:
    print(-1)
else:
    print(dijkstra(N, S))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

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

S = 0

def dijkstra(N, S):
    INF = 10**10
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] # ノード
        dis = q[0] # 過去に更新された最短距離

        # vまで2番目に短い距離（最新）　＜　過去最短距離　の時、
        # キューから取り出した過去のものを無視する
        if d[ver] < dis:
            continue

        # 隣接リストに対してループ
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

print(dijkstra(N, S))

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappush, heappop
read = sys.stdin.read


def main():
    N, M, *LRC = map(int, read().split())
    graph = [[(0, i - 1)] for i in range(N + 1)]
    graph[1] = []

    for L, R, C in zip(*[iter(LRC)] * 3):
        graph[L].append((C, R))

    distance = [-1] * (N + 1)
    queue = []
    heapify(queue)
    heappush(queue, (0, 1))

    while queue:
        cost, node = heappop(queue)
        if distance[node] == -1:
            distance[node] = cost
            for add_cost, next_node in graph[node]:
                if distance[next_node] == -1:
                    heappush(queue, (cost + add_cost, next_node))

    print(distance)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

E = sorted(E, key=lambda X: X[1])

# N_はN以上の2べき数
N_ = 2**(len(bin(N))-2)
INF = 10**10 # 10**10 
seg = [INF] * (2*N_-1)

# k番目(0index)をaに更新
def update(k, a):
    k += N_-1
    seg[k] = a

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

# 開区間！！！[a, b)の最小値を求める
def query(a, b, k, l, r):
    if r <= a or b <= l:
        return INF
    if a <= l and r <= b:
        return seg[k]
    else:
        vl = query(a, b, k*2+1, l, (l+r)//2)
        vr = query(a, b, k*2+2, (l+r)//2, r)
        return min(vl, vr)



# 初期化
update(0, 0)

for i in range(M):
    new = query(E[i][0], E[i][1], 0, 0, N_) + E[i][2]
    if new < seg[E[i][1] + N_-1]:
        update(E[i][1], new)

if seg[N-1+N_-1] == INF:
    print(-1)
else:
    print(seg[N-1+N_-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

E = sorted(E)

# N_はN以上の2べき数
N_ = 2**(len(bin(N))-2)
INF = 10**10 # 10**10 
seg = [INF] * (2*N_-1)

# k番目(0index)をaに更新
def update(k, a):
    k += N_-1
    seg[k] = a

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

# 開区間！！！[a, b)の最小値を求める
def query(a, b, k, l, r):
    if r <= a or b <= l:
        return INF
    if a <= l and r <= b:
        return seg[k]
    else:
        vl = query(a, b, k*2+1, l, (l+r)//2)
        vr = query(a, b, k*2+2, (l+r)//2, r)
        return min(vl, vr)



# 初期化
update(0, 0)

for i in range(M):
    new = query(E[i][0], E[i][1], 0, 0, N_) + E[i][2]
    if new < seg[E[i][1] + N_-1]:
        update(E[i][1], new)
if seg[N-1+N_-1] == INF:
    print(-1)
else:
    print(seg[N-1+N_-1])

Submission status: Wrong Answer

Solution code:
import sys

n, m = list(map(int, input().split()))
methods = []
for line in sys.stdin:
    l, r, c = map(int, line.split())
    methods.append((c, l - 1, r - 1))
methods.sort()

INF = 10 ** 18
jump = [-1] * n
cost = [0] * n

for c, l, r in methods:
    i = l
    while i < r:
        if jump[i] != -1:
            i = jump[i]
            continue
        jump[i] = r
        cost[i] = c
        i += 1

# print(jump)
# print(cost)
jump[-1] = n - 1

i = 0
r = jump[i]
ans = 0
n1 = n - 1
while i < n1:
    # print('i r', i, r)
    max_k, max_j = -1, -1
    for k in range(i + 1, r + 1):
        if jump[k] >= max_j:
            max_j = jump[k]
            max_k = k
    if max_k == -1:
        ans = -1
        break
    # print('k j', max_k, max_j)
    ans += cost[i]
    i = max_k
    r = max_j

print(ans)

Submission status: Wrong Answer

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]:
            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 == 10 ** 10:
    print(-1)
else:
    print(d)

Submission status: Wrong Answer

Solution code:
import heapq
import collections
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(dict)
    for i in range(N-1):
        graph[i+1][i] = 0

    for _ in range(M):
        L, R, C = map(int, input().split())
        graph[L-1][R-1] = C

    dist = [float('inf') for _ in range(N)]
    dist[0] = 0
    v = []
    heapq.heappush(v, [0, 0])

    while len(v) > 0:
        d, u = heapq.heappop(v)
        if d > dist[u]: continue
        for w in graph[u]:
            if dist[w] > d + graph[u][w]:
                dist[w] = d + graph[u][w]
                heapq.heappush(v, [dist[w], w])

    if dist[N-1] == float('inf'): return -1

    return dist[N-1]

if __name__ == '__main__':
    # main()
    print(main())

Submission status: Wrong Answer

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]:
            cost = repn[src][dest]
            if dist[dest] > prov_cost + 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 == 10 ** 10:
    print(-1)
else:
    print(d)

Submission status: Wrong Answer

Solution code:
import sys


class SegTreeMin:

    def __init__(self, n, max_v):
        self.n = n
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [max_v] * (n2 << 1)
        self.INF = max_v

    def update(self, i, x):
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
            i >>= 1

    def get_min(self, a, b):
        result = self.INF
        q = [(1, 0, self.n2)]
        while q:
            k, l, r = q.pop()

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

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

        return result


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    seg_tree = SegTreeMin(n, 10 ** 10)
    seg_tree.update(0, 0)
    lrc = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    lrc.sort()
    for l, r, c in lrc:
        l -= 1
        r -= 1
        tm = seg_tree.get_min(l, r)
        seg_tree.update(r, min(tm + c, seg_tree.get_min(r, r + 1)))
    mt = seg_tree.get_min(n-1, n)
    print(mt if mt != 10 ** 10 else -1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
inf = 10 ** 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 sys


class SegTreeMin:

    def __init__(self, n, max_v):
        self.n = n
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [max_v] * (n2 << 1)
        self.INF = max_v

    def update(self, i, x):
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
            i >>= 1

    def get_min(self, a, b):
        result = self.INF
        q = [(1, 0, self.n2)]
        while q:
            k, l, r = q.pop()

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

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

        return result


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    seg_tree = SegTreeMin(n, 10 ** 10)
    seg_tree.update(0, 0)
    lrc = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    lrc.sort()
    for l, r, c in lrc:
        l -= 1
        r -= 1
        tm = seg_tree.get_min(l, r + 1)
        seg_tree.update(r, min(tm + c, seg_tree.get_min(r, r + 1)))
    mt = seg_tree.get_min(n-1, n)
    print(mt if mt != 10 ** 10 else -1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline
input=sys.stdin.readline

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

def DIJKSTRA(point,d):
    cost      = [1e11]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

def main():
    
    d=[[]for i in range(n+1)]
    
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append((b,c))
    for i in range(1,n+1):
        d[i].append((i-1,0))
#    print(d)
    x=DIJKSTRA(1,d)[n]
    if x!=1e11:
        print(x)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline
input=sys.stdin.readline

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

def DIJKSTRA(point,d):
    cost      = [1e11]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    print(cost)
    return cost

def main():
    
    d=[[]for i in range(n+1)]
    
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append((b,c))
    for i in range(1,n+1):
        d[i].append((i-1,0))
#    print(d)
    x=DIJKSTRA(1,d)[n]
    if x!=1e11:
        print(x)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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]:
            cost = repn[src][dest]
            if dist[dest] > prov_cost + 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())
    repn[l][r] = c

d = dijkstra(repn, 1, N)

if d == 10 ** 10:
    print(-1)
else:
    print(d)

Submission status: Wrong Answer

Solution code:
import heapq
import collections
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(dict)
    for i in range(1, N):
        graph[i+1][i] = 0

    for _ in range(M):
        L, R, C = map(int, input().split())
        graph[L][R] = C

    dist = [float('inf') for _ in range(N)]
    dist[0] = 0
    v = []
    heapq.heappush(v, [0, 1])

    while v:
        d, u = heapq.heappop(v)
        if d <= dist[u-1]:
            for w in graph[u]:
                if dist[w-1] > d + graph[u][w]:
                    dist[w-1] = d + graph[u][w]
                    heapq.heappush(v, [dist[w-1], w])

    if dist[N-1] == float('inf'): return -1

    return dist[N-1]

if __name__ == '__main__':
    # main()
    print(main())

Submission status: Wrong Answer

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]:
            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())
    repn[l][r] = c

d = dijkstra(repn, 1, N)

if d == 10 ** 10:
    print(-1)
else:
    print(d)

Submission status: Wrong Answer

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



def dijkstra(repn, start, goal):
    
    num = N + 1          # グラフのノード数
    dist = [inf for i in range(num)] # 始点から各頂点までの最短距離を格納する
    
    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]:
            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())
    repn[l][r] = c

d = dijkstra(repn, 1, N)

if d == 10 ** 10:
    print(-1)
else:
    print(d)

Submission status: Wrong Answer

Solution code:
import heapq
import collections
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(dict)
    for i in range(N-1):
        graph[i+1][i] = 0

    for _ in range(M):
        L, R, C = map(int, input().split())
        graph[L-1][R-1] = C

    dist = [float('inf') for _ in range(N)]
    dist[0] = 0
    v = []
    heapq.heappush(v, [0, 0])

    while v:
        d, u = heapq.heappop(v)
        if d > dist[u]: continue
        for w in graph[u]:
            if dist[w] > d + graph[u][w]:
                dist[w] = d + graph[u][w]
                e = d + graph[u][w]
                heapq.heappush(v, [e, w])

    if dist[N-1] == float('inf'): return -1

    return dist[N-1]

if __name__ == '__main__':
    # main()
    print(main())

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
edge = []
for i in range(M):
    a, b, c = map(int, input().split())
    edge.append((a-1, b-1, c))

edge = sorted(edge)
DEKAI = 10 ** 18
dp = [DEKAI] * N
dp[0] = 0
min_L = 0
B = []
for a, b, c in edge:
    if dp[a] == DEKAI:
        idx = bisect.bisect_left(B, a+1)
        if idx > len(B) - 1:
            break
        dp[b] = min(dp[b], dp[B[idx]] + c) 
    else:
        dp[b] = min(dp[b], dp[a] + c)
    B.append(b)

if dp[N-1] == DEKAI:
    print(-1)
else:
    print(dp[N-1])

Submission status: Wrong Answer

Solution code:
import heapq
import collections
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(dict)
    for i in range(N-1):
        graph[i+1][i] = 0

    for _ in range(M):
        L, R, C = map(int, input().split())
        graph[L-1][R-1] = C

    dist = [float('inf') for _ in range(N)]
    dist[0] = 0
    v = []
    heapq.heappush(v, [0, 0])
    while v:
        d, u = heapq.heappop(v)
        if d > dist[u]: continue
        for w in graph[u]:
            if dist[w] > d + graph[u][w]:
                dist[w] = d + graph[u][w]
                heapq.heappush(v, [dist[w], w])


    if dist[N-1] == float('inf'): return -1
    return dist[N-1]

if __name__ == '__main__':
    # main()
    print(main())

Submission status: Wrong Answer

Solution code:
import heapq
import collections
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(dict)
    for i in range(N-1):
        graph[i+1][i] = 0

    for _ in range(M):
        L, R, C = map(int, input().split())
        graph[L-1][R-1] = C
        graph[R-1][L-1] = C

    dist = [float('inf') for _ in range(N)]
    dist[0] = 0
    v = []
    heapq.heappush(v, [0, 0])
    while v:
        d, u = heapq.heappop(v)
        if d > dist[u]: continue
        for w in graph[u]:
            if dist[w] > d + graph[u][w]:
                dist[w] = d + graph[u][w]
                heapq.heappush(v, [dist[w], w])


    if dist[N-1] == float('inf'): return -1
    return dist[N-1]

if __name__ == '__main__':
    # main()
    print(main())

Submission status: Wrong Answer

Solution code:
import heapq
N,M=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    l,r,c=map(int,input().split())
    G[l-1][r-1]=c
for i in range(1,N):
    G[i][i-1]=0
def dijkstra(adj, st):
    dist=[10**15 for i in range(N)]
    dist[st]=0
    q=[]
    heapq.heappush(q,(0,st))
    while (len(q)!=0):
        prc,src=heapq.heappop(q)
        if dist[src]<prc:
            continue
        for dest in adj[src]:
            cost=adj[src][dest]
            if dist[dest]>dist[src]+cost:
                dist[dest]=dist[src]+cost
                heapq.heappush(q,(dist[dest],dest))                
    return dist
ans=dijkstra(G,0)[-1]
if ans==10**15:
    ans=-1
print(ans)