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())
X = [list(map(int, input().split())) for _ in range(M)]

edges = [[] for _ in range(N)]
for u, v, c in X:
    edges[u - 1].append((v - 1, c))
    
for i in range(N - 1):
    edges[i + 1].append((i, 0))

INF = 10 ** 9 + 7
d = [INF] * N
d[0] = 0

visited = [False] * N
visited[0] = True

# Priority queue (cost, node)
pq = []
heappush(pq, (0, 0))

while len(pq) > 0:
    cost, u = heappop(pq)
    visited[u] = True
    
    # Search nodes connected with target node 'u'
    for v, c in edges[u]:
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            
print(d[-1] if d[-1] != INF else -1)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
    
edges = X[:]
for i in range(1, N):
    edges.append([i + 1, i, 0])
    
INF = 10 ** 9 + 7
d = [INF] * N
d[0] = 0

visited = [False] * N
visited[0] = True

# Priority queue (cost, node)
pq = []
heappush(pq, (0, 0))

while len(pq) > 0:
    cost, u = heappop(pq)
    visited[u] = True
    
    # Search nodes connected with target node 'u'
    for v, w, c in edges:            
        node = w - 1
        if v - 1 != u or visited[node]:
            continue

        if d[node] > d[u] + c:
            d[node] = d[u] + c
            heappush(pq, (d[node], node))
                   
print(d[-1] if d[-1] != INF else -1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N, M = list(map(int, input().split()))

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

# if RCL[0][0] != -(N-1):
#    print(-1)
#    sys.exit(0)


D = deque()

for rcl in RCL:
    r, c, l = rcl
    r = -r
    if r == N-1:
        D.append((c, l))
    else:
        nex = deque()
        m = 10**16
        while D:
            d = D.popleft()
            if l < d[1] <= r:
                nex.append(d)
                if m > d[0] + c:
                    m = d[0] + c
        if m != 10**16:
            nex.append((m, l))
        D = nex

ans = 10**16

while D:
    d = D.popleft()
    if d[1] == 0 and ans > d[0]:
        ans = d[0]

if ans == 10**16:
    print(-1)
    sys.exit(0)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdout
import heapq
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def dumpheap(h):
    a = []
    print("- -")
    while len(h)>0:
        z = heapq.heappop(h)
        print(z)
        a.append(z)
    for z in a:
        heapq.heappush(h,z)

n,m = inm()
a = []
for i in range(m):
    l,r,c = inm()
    a.append((l,r,c))
a.sort()
if a[0][0]>1:
    print(-1)
    exit()

ddprint(a)

h = []
top = 0
for i in range(m):
    l,r,c = a[i]
    if l==1:
        heapq.heappush(h,(c,0,l,r,c))
    else:
        top = i
        break

if DBG:
    dumpheap(h)

curld,curd,curl,curr,curc = heapq.heappop(h)
for i in range(top,m):
    l,r,c = a[i]
    while curr<l:
        if len(h)==0:
            print(-1)
            exit()
        curld,curd,curl,curr,curc = heapq.heappop(h)
    ddprint("push {} {} {} {} {}".format(curld+c,curld,l,r,c))
    heapq.heappush(h,(curld+c,curld,l,r,c))

r=0
while r<n:
    if len(h)==0:
            print(-1)
            exit()
    ld,d,l,r,c = heapq.heappop(h)
print(ld)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N, M = list(map(int, input().split()))

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

# if RCL[0][0] != -(N-1):
#    print(-1)
#    sys.exit(0)


D = deque()

for rcl in RCL:
    r, c, l = rcl
    r = -r
    if r == N-1:
        D.append((c, l))
    else:
        nex = deque()
        while D:
            d = D.popleft()
            if l < d[1] <= r:
                nex.append(d)
                nex.append((d[0] + c, l))

        D = nex

ans = 10**16

while D:
    d = D.popleft()
    if d[1] == 0 and ans > d[0]:
        ans = d[0]

if ans == 10**16:
    print(-1)
    sys.exit(0)
print(ans)

Submission status: Wrong Answer

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

INF = float('inf')

def solve():
    N, M = map(int, input().split())
    Es = []
    for _ in range(M):
        L, R, C = map(int, input().split())
        L, R = L-1, R-1
        Es.append((L, R, C))

    Es.sort()

    PQ = [(0, 0)]

    dists = [INF] * N
    iE = 0
    for tm in range(N):
        while PQ:
    #        dist, R = heappop(PQ)
            dist, R = PQ[0]
            if tm <= R:
                break
            heappop(PQ)
        else:
            return -1

        dists[tm] = dist
        while iE < M and Es[iE][0] == tm:
            L, R, C = Es[iE]
            PQ.append((dist+C, R))
            iE += 1

    return dists[-1]


print(solve())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split(' '))

tree_list = []
for _ in range(M):
    L,R,C = map(int,input().split(' '))
    tree_list.append([R-1,L-1,C])
    '''
    if (R-1) in tree_list[L-1].keys():
        tree_list[L-1][R-1] = min(tree_list[L-1][R-1],C)
    else:
        tree_list[L-1][R-1] = C
    '''
tree_list.sort(reverse=True)
dp = [1000000000] * N
dp[N-1] = 0
current_num = -1
flag = False
for path in tree_list:
    if dp[path[0]] == 1000000000:
        flag = True
        break
    if dp[path[1]] > dp[path[0]] + path[2]:
        for i in range(path[1],path[0]):
            if (dp[path[0]] + path[2]) < dp[i]:
                dp[i] = dp[path[0]] + path[2]
            else:
                break 
if dp[0] == 1000000000 or flag:
    print(-1)
else:
    print(dp[0])

Submission status: Wrong Answer

Solution code:
[N,M] = list(map(int,input().split()))

LRC = []
for i in range(M):
    tmp = list(map(int,input().split()))
    LRC.append((tmp[0],tmp[1],tmp[2]))

LRC = sorted(LRC, key=lambda x: (x[1], x[0], x[2]))

cnt = [2*10**9]*N
cnt[0] = 0

t=1
p=0
inv = 2*10**9
while p<M:
    L=LRC[p][0]
    R=LRC[p][1]
    C=LRC[p][2]
    if t >=R:
        t = R-1
    while t < R:
        cnt[t]=min(cnt[L-1]+C,cnt[t],inv+C)
        if cnt[t]<cnt[t-1]:
            inv = cnt[t]
        t+=1
    p+=1


if cnt[-1]==2*10**9:
    print(-1)
else:
    print(cnt[-1])

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(m)]
    a.sort()
    dp = [10 ** 10 for i in range(n)]
    dp[0] = 0
    for l, r, c in a:
        tp = dp[l - 1] + c
        for i in range(l - 1, r):
            dp[i] = min(dp[i], tp)
    if dp[-1] == 10 ** 18:
        print(-1)
    else:
        print(dp[-1])


main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline

N, M = map(int, input().split())
d = []


# N: 処理する区間の長さ

INF = 2**31-1

LV = (N).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)
    f = 0
    if l > 1:
      f = query(l, r)
    #print(f, l, r)
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            yl = INF
            if lazy[R-1] != None: yl = lazy[R-1]
            lazy[R-1] = data[R-1] = min(x + f, data[R-1] + x,yl)
        if L & 1:
            yl = INF
            if lazy[L-1] != None: yl = lazy[L-1]
            lazy[L-1] = data[L-1] = min(x + f, data[L-1] + x,yl)
            L += 1
        L >>= 1; R >>= 1
    #print(data)
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])


for _ in range(M):
  d.append(list(map(int, input().split())))
d.sort(key = lambda x: (x[0], x[1]))
#print(d)
for i in range(M):
  update(d[i][0], d[i][1] + 1, d[i][2])
  #print(d[i])
  #print(data)

res = query(N, N + 1)
if res != INF: print(res)
else: print(-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]

s = sorted(s, key=lambda x:x[0])
N += 1
# N: 処理する区間の長さ
INF = 2**31-1
LV = (N-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    min_value = query(l, r)
    # print(min_value, x)
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            if lazy[R-1] == None:
                lazy[R-1] = min_value + x
                # data[R-1] = min_value + x
            else:
                lazy[R-1] = min(lazy[R-1], min_value + x)
            data[R-1] = min(data[R-1], min_value + x)
        if L & 1:
            if lazy[L-1] == None:
                lazy[L-1] = min_value + x
                # data[L-1] = min_value + x
            else:
                lazy[L-1] = min(lazy[L-1], min_value + x)
            data[L-1] = min(data[L-1], min_value + x)
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])
    # print(data, lazy)

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

update(1, 2, -INF)
for i in range(m):
    l = s[i][0]
    r = s[i][1]
    c = s[i][2]

    update(l, r+1, c)
    # print(query(4, 5))

tmp = query(N-1, N)
if tmp == INF:
    print(-1)
else:
    print(tmp)

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    input = sys.stdin.readline

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

    LRC.sort(key=lambda x: (x[0], x[1]))
    # print(LRC)

    if M == 1:
        l, r, c = LRC[0]
        if l == 1 and r == N:
            print(c)
        else:
            print(-1)
            exit()
        

    dp = [10 ** 9 + 10] * (N + 1)
    dp[1] = 0

    sml, big = LRC[0][0], LRC[0][1]



    for i in range(1, M):
        l, r, c = LRC[i]
        if l <= big:
            if big <= r:
                big = r
        else:
            print(-1)
            exit()

    if sml != 1 or big != N:
    
        print(-1)
        exit()

    
    for lrc in LRC:
        l, r, c = lrc
        for i in range(l, r + 1):

            dp[i] = min(dp[i], dp[l] + c)
            
    
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

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

Submission status: Wrong Answer

Solution code:
import heapq
import bisect
n, m = map(int, input().split())
li = [list(map(int, reversed(input().split()))) for _ in range(m)]
li.sort(key=lambda x: x[2])
a = [x[2] for x in li]
idx = 0
t = 1
hq = []
d = [0] * n
while t < n:
    idxx = bisect.bisect_right(a, t)
    for i in range(idx, idxx):
        heapq.heappush(hq, li[i])
    idx = idxx
    if not hq:
        print(-1)
        exit(0)
    c, r, l = heapq.heappop(hq)
    for i in range(t, r):
        d[i] = d[l - 1] + c
    t = max(t, r)
print(d[n - 1])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lrc = []
for _ in range(m):
  lrc.append(list(map(int,input().split())))
import heapq
heapq.heapify(lrc)
arrive = [[1,0]]
heapq.heapify(arrive)
#print(arrive)
while True:
  if arrive == []:
    print(-1)
    break
  point,dis = heapq.heappop(arrive)
  if point == n:
    print(dis)
    break
  if arrive != []:
    if dis > arrive[0][1]:
      continue
  while True:
    if lrc == []:
      break
    if lrc[0][0] <= point:
      l,r,c = heapq.heappop(lrc)
      if l <= point < r:
        heapq.heappush(arrive,[r,dis+c])
    else:
      break
  #print(arrive)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lrc = []
for _ in range(m):
  lrc.append(list(map(int,input().split())))
import heapq
heapq.heapify(lrc)
arrive = [[1,0]]
heapq.heapify(arrive)
#print(arrive)
while True:
  if arrive == []:
    print(-1)
    break
  point,dis = heapq.heappop(arrive)
  if point == n:
    print(dis)
    break
  if arrive != []:
    if dis > arrive[0][1]:
      continue
  while True:
    if lrc == []:
      break
    if lrc[0][0] <= point:
      l,r,c = heapq.heappop(lrc)
      if l <= point < r:
        heapq.heappush(arrive,[r,dis+c])
    else:
      break
  print(arrive)

Submission status: Wrong Answer

Solution code:
[N,M] = list(map(int,input().split()))

LRC = []
for i in range(M):
    tmp = list(map(int,input().split()))
    LRC.append((tmp[0],tmp[1],tmp[2]))

LRC = sorted(LRC, key=lambda x: (x[1], x[2], x[0]))

cnt = [2*10**9]*N
cnt[0] = 0

t=1
p=0
inv = 2*10**9
while p<M:
    L=LRC[p][0]
    R=LRC[p][1]
    C=LRC[p][2]
    if t >=R:
        t = R-1
    while t < R:
        cnt[t]=min(cnt[L-1]+C,cnt[t],inv+C)
        if cnt[t]<cnt[t-1]:
            inv = cnt[t]
        t+=1
    p+=1


if cnt[-1]==2*10**9:
    print(-1)
else:
    print(cnt[-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
#import math
#import time
import random  # randome is not available at Codeforces
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#eps=10**(-10)
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True


n,m=LI()
d=[inf]*(n+1)
dp=[inf]*(n+1)
s_dp=[inf]*(n+1)
dp[1]=0
s_dp[1]=0
path=[[] for _ in range(n+1)]
for i in range(m):
    l,r,c=LI()
    #l,r=l-1,r-1
    path[l].append((l,r,c))
    show([0]*l+[c]*(r-l)+[0]*(n-r-1))
    for i in range(l,r):
        d[i]=min(d[i],c)

q_g=[[] for _ in range(1+n)]
q_s=[[] for _ in range(1+n)]
for x in range(1,n):
    # 新規パスのスタック
    for p in path[x]:
        q_s[x].append(p)
        l,r,c=p
        q_g[r].append(p)
    
    # 終点になるパスの処理
    while q_g[x+1]:
        l,r,c=q_g[x+1].pop()
        dp[x+1]=min(dp[x+1],dp[l]+c)

show()
show(dp)
show(d)
for i in groupby(d):
    show(i[0],end=' ')

Submission status: Wrong Answer

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d



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

edge = [[] for i in range(n)] #edge[i] : iから出る道の[重み,行先]の配列

l=[list(map(int,input().split())) for i in range(m)]
for i in range(m):
    x,y,z =l[i][0],l[i][1],l[i][2]
    x-=1
    y-=1
    edge[x].append([z,y])
    edge[y].append([z,x]) 
#print(edge)
#print(dijkstra_heap(0))
a=dijkstra_heap(0)
for i in range(n-2,-1,-1):
    if a[i]>a[i+1]:
        a[i]=a[i+1]
l.sort()
for i in range(m):
    a[l[i][1]-1]=min(a[l[i][1]-1],a[l[i][0]-1]+l[i][2])
if a[-1]==float('inf'):
    print(-1)
else:
    print(a[-1])

Submission status: Wrong Answer

Solution code:
import collections
import heapq
import itertools

class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        #0-indexedでなくてもよいことに注意
        #u = from, v = to, d = cost
        #directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]


N,M = map(int, input().split())
lrc = [list(map(int, input().split())) for i in range(M)]

grp = Dijkstra()

for i in lrc:
    ptn = list(itertools.combinations(range(i[0], i[1] + 1),2))
    for p in ptn:
        grp.add(p[0], p[1], i[2])

print(grp.Dijkstra_search(1)[0][N])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

    while q:
        y, z = heappop(q)
        if y >= l:
            heappush(q, (y, z))
            break

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

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

# print(q)

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

print(ans)

Submission status: 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 time import* 
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
t=time()

def main():
    n,m=map(int,input().split())
    x=[tuple(map(int,input().split()))for i in range(m)]
    y=sorted(x)
    start=set()
    for s,t,r in y:
        if s==1:
            start.add((1,t,r))
    ans=set([-1])
    substart=set()
    while 1:
        while start:
            qp,p,q=start.pop()
            for s,t,r in y:
                if t==n:
                    ans.add(q)
                elif s<=p and p<=t and s!=qp:
                    substart.add((p,t,q+r))
                    
        start=substart
        if time()-t>1.9:
            if len(ans)!=1:
                print(min(i for i in ans if i!=-1))
            else:
                print(-1)
            exit()
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())

edges=[]
edge=[]
v=[]
rss=[0]
inf=float('inf')

for i in range(m):
    l,r,c=map(int,input().split())
    edges.append((l-1,r-1,c))
    #rs.append(l-1)
    rss.append(r-1)
edges.append((n-1,n-1,0))
edges.sort()
rss.sort()
rs=[rss[0]]
for i in range(m):
    if edges[i][0]==edges[i+1][0] and edges[i][1]<=edges[i+1][1] and edges[i][2]>=edges[i+1][2]:
        continue
    edge.append(edges[i])
for i in range(1,m+1):
    #print(rs)
    if rs[-1]!=rss[i]:
        rs.append(rss[i])
dp=[inf]*(len(rs))
dp[0]=0
if rs[-1]!=n-1:
    print(-1)
    sys.exit()
import bisect
for i in range(len(edge)):
    l,r,c=edge[i]
    idx=bisect.bisect_left(rs,r)
    idx2=bisect.bisect_left(rs,l)
    dp[idx]=min(dp[idx],dp[idx2]+c)
print(dp[-1] if dp[-1]!=inf else -1)

Submission status: Wrong Answer

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

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:
            jump[i] = r
            cost[i] = c
            i += 1
            continue
        i = jump[i]

i = 0
ans = 0
n1 = n - 1
while i < n1:
    if jump[i] == -1:
        print(-1)
        exit()
    ans += cost[i]
    i = jump[i]

print(ans)

Submission status: Wrong Answer

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

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

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

    while q:
        y, z = heappop(q)
        if y >= l:
            heappush(q, (y, z))
            break

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

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

# print(q)

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

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
LRCs = []
for i in range(M):
  L, R, C = map(int, input().split())
  L, R = L-1, R-1
  LRCs.append((L, R, C))
LRCs.sort()
#print(LRCs)
Ds = [-1]*N
Ds[0] = 0
Rs = sorted([0]+[R for L, R, C in LRCs])
#print(Rs)
for L, R, C in LRCs:
  i = bisect.bisect_left(Rs, L)
  j = bisect.bisect_left(Rs, R)
  #print(i, j)
  if i == len(Rs):
    continue
  L = Rs[i]
  #print(L, Ds)
  if Ds[L] < 0:
    continue
  if Ds[R] < 0:
    Ds[R] = Ds[L]+C
  else:
    Ds[R] = min(Ds[R], Ds[L]+C)
r = Ds[-1]
print(r)

Submission status: Wrong Answer

Solution code:
N,M=[int(s) for s in input().split()]
ls=[[int(s) for s in input().split()] for i in range(M)]
ls.sort()
#print(ls)
path=[[1,0]]
t=1
flag=0
for e in ls:
  if e[0]>t:
    print(-1)
    flag=1
    break
  else:
    m=[f for f in path if f[0]>=e[0]]
    #print(m)
    path.append([e[1],m[0][1]+e[2]])
    t=max([t,e[1]])
    path.sort()
if flag==0:
  ans=[f for f in path if f[0]>=N]
  print(ans[0][1])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split(' '))

tree_list = []
for _ in range(M):
    L,R,C = map(int,input().split(' '))
    tree_list.append([R-1,L-1,C])
    '''
    if (R-1) in tree_list[L-1].keys():
        tree_list[L-1][R-1] = min(tree_list[L-1][R-1],C)
    else:
        tree_list[L-1][R-1] = C
    '''
tree_list.sort(reverse=True)
dp = [1000000000] * N
dp[N-1] = 0
for path in tree_list:
    if dp[path[1]] > dp[path[0]] + path[2]:
        for i in range(path[1],path[0]):
            if (dp[path[0]] + path[2]) < dp[i]:
                dp[i] = dp[path[0]] + path[2]
            else:
                break 
if dp[0] == 1000000000:
    print(-1)
else:
    print(dp[0])