Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

 フクロモモンガ(Sugar Glider)

フクロモモンガのJOI 君が住んでいる森にはユーカリの木が $N$ 本生えており，それらの木には1 から $N$ の番号がついている．木 $i$ の高さは $H_i$ メートルである．

JOI 君が相互に直接飛び移ることのできる木の組が $M$ 組あり，各組の木の間を飛び移るためにかかる時間が定まっている．JOI 君が木の間を飛び移っている間は，地面からの高さが1 秒あたり1 メートル下がる．すなわち，JOI 君の現在の地面からの高さが $h$ メートル，木の間を飛び移るためにかかる時間が $t$ 秒であるとき，飛び移った後の地面からの高さは $h - t$ メートルとなる．ただし，$h - t$ が0 よりも小さくなる場合や行き先の木の高さよりも大きくなる場合は飛び移ることができない．

さらに，JOI 君は木の側面を上下に移動することによって，地面からの高さを0 メートルから今いる木の高さの範囲で増減させることができる．JOI 君が地面からの高さを1 メートル増加または減少させるためには1 秒の時間がかかる．

JOI 君は，木1 の高さ$X$ メートルの位置から木$N$ の頂上(高さ$H_N$ メートルの位置) に行こうとしており，そのためにかかる時間の最小値を知りたい．

課題

各木の高さと，JOI 君が直接飛び移ることができる木の組の情報と，最初JOI 君がいる場所の高さが与えられる．木 $N$ の頂上に行くためにかかる時間の最小値を求めるプログラムを作成せよ.

入力

標準入力から以下のデータを読み込め．

1 行目には，整数 $N, M, X$ が空白を区切りとして書かれている．これは，木の本数が $N$ 本，移動できる木の組が $M$ 組あり，最初JOI 君が木1 の高さ $X$ メートルの位置にいることを表す．

続く $N$ 行のうちの $i$ 行目$(1 \leq i \leq N)$ には，整数 $H_i$ が書かれている．これは，木 $i$ の高さが $H_i$ メートルであることを表す．

続く$M$ 行のうちの $j$ 行目$(1 \leq j \leq M)$ には，整数 $A_j, B_j, T_j$ $(1 \leq A_j \leq N, 1 \leq B_j \leq N, A_j \ne B_j)$ が空白を区切りとして書かれている．これは，木 $A_j$ と木 $B_j$ の間を相互に $T_j$ 秒で飛び移ることができることを表している．また，$1 \leq j 情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20


Sample output:
110

Submission status: Memory Limit Exceeded

Solution code:
from heapq import heappop, heappush
import sys

N, M, X = map(int, input().split())
tree_height = [0]+[int(sys.stdin.readline()) for _ in [0]*N]
edges = [[] for _ in [0]*(N+1)]
for a, b, t in (map(int, l.split()) for l in sys.stdin):
    edges[a].append((b, t))
    edges[b].append((a, t))

pq = [(0, 1, X)]
while pq:
    time, v, height = heappop(pq)
    if v == N:
        print(time+(tree_height[v]-height))
        exit()

    max_height = tree_height[v]
    for to, dist in edges[v]:
        if max_height - dist < 0:
            continue
        new_height = height - dist
        new_time = time + dist
        if new_height < 0:
            heappush(pq, (new_time-new_height, to, 0))
        elif new_height > tree_height[to]:
            heappush(pq, (new_time+(new_height-tree_height[to]), to, tree_height[to]))
        else:
            heappush(pq, (new_time, to, new_height))
        
print(-1)

Submission status: Memory Limit Exceeded

Solution code:
from heapq import heappush, heappop


def dijkstra():
    g = n - 1
    heap = [(-x, 0, 0)]  # estimate(cost-height), cost, tree
    visited = [float('inf')] * n
    while heap:
        est, cost, tree = heappop(heap)
        h = cost - est
        if tree == g:
            return cost + trees[tree][0] - h
        if visited[tree] < est:
            continue
        visited[tree] = est
        for t, tree2 in trees[tree][1]:
            ht = trees[tree2][0]
            if t > h:
                new_cost = cost + t + t - h
                new_h = 0
            elif h - t > ht:
                new_cost = cost + h - ht
                new_h = ht
            else:
                new_cost = cost + t
                new_h = h - t
            new_est = new_cost - new_h
            heappush(heap, (new_est, new_cost, tree2))
    return -1


n, m, x = map(int, input().split())
trees = [[int(input()), set()] for i in range(n)]
for _ in range(m):
    a, b, t = map(int, input().split())
    a -= 1
    b -= 1
    if trees[a][0] >= t:
        trees[a][1].add((t, b))
    if trees[b][0] >= t:
        trees[b][1].add((t, a))
print(dijkstra())

Submission status: Memory Limit Exceeded

Solution code:
from heapq import heappush, heappop


def dijkstra():
    g = n - 1
    heap = [(-x, 0, 0)]  # estimate(cost-height), cost, tree
    visited = [float('inf')] * n
    while heap:
        est, cost, tree = heappop(heap)
        h = cost - est
        if tree == g:
            return cost + trees[tree][0] - h
        if visited[tree] < est:
            continue
        visited[tree] = est
        for t, tree2 in trees[tree][1]:
            ht = trees[tree2][0]
            if t > h:
                new_cost = cost + t + t - h
                new_h = 0
            elif h - t > ht:
                new_cost = cost + h - ht
                new_h = ht
            else:
                new_cost = cost + t
                new_h = h - t
            new_est = new_cost - new_h
            if visited[tree2] > new_est:
                heappush(heap, (new_est, new_cost, tree2))
    return -1


n, m, x = map(int, input().split())
trees = [[int(input()), set()] for i in range(n)]
for _ in range(m):
    a, b, t = map(int, input().split())
    a -= 1
    b -= 1
    if trees[a][0] >= t:
        trees[a][1].add((t, b))
    if trees[b][0] >= t:
        trees[b][1].add((t, a))
print(dijkstra())

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys

N, M, X = map(int, input().split())
tree_height = [0]+[int(sys.stdin.readline()) for _ in [0]*N]
edges = [[] for _ in [0]*(N+1)]
for a, b, t in (map(int, l.split()) for l in sys.stdin):
    edges[a].append((b, t))
    edges[b].append((a, t))

vertices = [float("inf")]*(N+1)
pq = [(0, 1, X)]
while pq:
    time, v, height = heappop(pq)
    if v == N:
        print(time+(tree_height[v]-height))
        exit()
    if time > vertices[v]:
        continue

    max_height = tree_height[v]
    for to, dist in edges[v]:
        if max_height - dist < 0:
            continue
        new_height = height - dist
        new_time = time + dist
        if new_height < 0:
            new_time, new_height = new_time-new_height, 0
        elif new_height > tree_height[to]:
            new_time, new_height = new_time+(new_height-tree_height[to]), tree_height[to]

        if vertices[to] > new_time:
            vertices[to] = new_time
            heappush(pq, (new_time, to, new_height))
        
print(-1)

Submission status: Accepted

Solution code:
import sys
import heapq

f = sys.stdin

n,m,x = map(int,f.readline().split())
h = [None] + [int(f.readline()) for _ in range(n)]
tuple_abt = [tuple(map(int, line.split())) for line in f]

dict_abt = {}
for ai,bi,ti in tuple_abt:
    try:
        if ti <= h[ai]:
            dict_abt[ai][bi] = ti
    except KeyError:
        dict_abt[ai] = {bi:ti}
    try:
        if ti <= h[bi]:
            dict_abt[bi][ai] = ti
    except KeyError:
        dict_abt[bi] = {ai:ti}

class Tree:
    def __init__(self, t, h, jump_t=0, next_h=0):
        if jump_t:
            t += jump_t
            h -= jump_t
            if h < 0:# 登って辻褄を合わせる
                t += -h
                h = 0
            if next_h < h:# 降りて辻褄を合わせる
                t += h - next_h
                h = next_h
        self.t = t
        self.h = h
        self.d = t - h #基本的に高い位置の方が早い為

d = [None] * (n + 1)
d[1] = Tree(0, x)
q = [(d[1].d, 1)] # (d(v), v)
while len(q):
    _, u = heapq.heappop(q) #コストが最小の木を取得
    if u not in dict_abt:
        continue
    for v, t in dict_abt[u].items():
        dv = Tree(d[u].t, d[u].h, t, h[v])
        if d[v] == None or d[v].d > dv.d:
            d[v] = dv
            heapq.heappush(q,(d[v].d, v))
if d[-1]:
    print(d[-1].t + h[-1] - d[-1].h)
else:
    print(-1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


def dijkstra():
    g = n - 1
    heap = [(-x, 0, 0)]  # estimate(cost-height), cost, tree
    visited = [float('inf')] * n
    while heap:
        est, cost, tree = heappop(heap)
        h = cost - est
        if tree == g:
            return cost + trees[tree][0] - h
        if visited[tree] <= est:
            continue
        visited[tree] = est
        for t, tree2 in trees[tree][1]:
            ht = trees[tree2][0]
            if t > h:
                new_cost = cost + t + t - h
                new_h = 0
            elif h - t > ht:
                new_cost = cost + h - ht
                new_h = ht
            else:
                new_cost = cost + t
                new_h = h - t
            new_est = new_cost - new_h
            if visited[tree2] >= new_est:
                heappush(heap, (new_est, new_cost, tree2))
    return -1


n, m, x = map(int, input().split())
trees = [[int(input()), set()] for i in range(n)]
for _ in range(m):
    a, b, t = map(int, input().split())
    a -= 1
    b -= 1
    if trees[a][0] >= t:
        trees[a][1].add((t, b))
    if trees[b][0] >= t:
        trees[b][1].add((t, a))
print(dijkstra())

Submission status: Accepted

Solution code:
# AOJ 0601 Sugar Glider
# Python3 2018.7.4 bal4u

import sys
from sys import stdin
input = stdin.readline

import heapq
def dijkstra(V, to, start, goal, x):
	Q = []
	visited = [0]*V
	heapq.heappush(Q, (-x, start))
	while Q:
		t, s = heapq.heappop(Q)
		t = -t
		if s == goal: return x+h[goal]-t*2
		if visited[s]: continue
		visited[s] = 1
		for e, c in to[s]:
			if visited[e] or c > h[s]: continue
			d = min(h[e], t-c)
			heapq.heappush(Q, (-d, e))
	return -1
	
n, m, x = map(int, input().split())
h = [int(input()) for i in range(n)]
to = [[] for i in range(n)]
for i in range(m):
	a, b, t = map(int, input().split())
	a, b = a-1, b-1
	to[a].append((b, t))
	to[b].append((a, t))
print(dijkstra(n, to, 0, n-1, x))

Submission status: Accepted

Solution code:
import heapq
from collections import deque

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

adj_list = [ [] for _ in range(N+1)]
for _ in range(M):
  u,v,c = map(int,input().split())
  # adj_list[u].append((v,c))
  # adj_list[v].append((u,c))
  if H[u] >= c: adj_list[u].append((v,c))
  if H[v] >= c: adj_list[v].append((u,c))

INF = float('inf')
visited = [False] * (N+1)
costs = [INF] * (N+1)

# q=time,neighbor,cur_h
q = [(0,1,X)]
costs[1] = 0
last_position = 0
while q:
  cost,n,h = heapq.heappop(q)
  visited[n] = True
  if n == N: 
    last_position = h
    break

  for nei,nc in adj_list[n]:
    if visited[nei]: continue
    # p-nt < 0        => ntの高さまで上る
    # p-nt > H[nei]   => 最低限下りられるところまで
    #    　　　　　       もしも下りられなかったらFalse
    # 0 <= p-nt <= nt => 普通に飛び移れる
    if h-nc < 0:
      # import pdb; pdb.set_trace()
      climbUp = (nc-h)
      if climbUp > H[n]: continue
      nextCost = cost + climbUp + nc
      nextH = 0
    elif h-nc > H[nei]:
      # import pdb; pdb.set_trace()
      climbDown = (h-(H[nei]+nc))
      if climbDown < 0: continue
      nextCost = cost + climbDown + nc
      nextH = H[nei]
    else:
      nextCost = cost + nc
      nextH = h - nc
    
    if nextCost < costs[nei]:
      costs[nei] = nextCost
      heapq.heappush(q, (nextCost, nei, nextH))
    # print(q)

if costs[N] == INF:
  print(-1)
else:
  print(costs[N] + H[N]-last_position)

Submission status: Accepted

Solution code:
def solve():
    from heapq import heappop, heappush
    from sys import stdin
    f_i = stdin
    
    N, M, X = map(int, f_i.readline().split())
    H = [None] + [int(f_i.readline()) for i in range(N)]
    
    adj = [[] for i in range(N + 1)]
    for i in range(M):
        A, B, T = map(int, f_i.readline().split())
        adj[A].append((B, T))
        adj[B].append((A, T))
    
    hq = [(0, 1, X)] # element: (cost, tree number, height)
    unvisited = [True] * (N + 1)
    cost = [100000000000000] * (N + 1)
    
    # Dijkstra's algorithm with priority queue
    while hq:
        c1, n1, h1 = heappop(hq)
        
        if n1 == N:
            print(c1 + (H[N] - h1))
            break
        
        unvisited[n1] = False
        
        for n2, t2 in adj[n1]:
            if unvisited[n2]:
                h3 = h1 - t2
                if h3 < 0:
                    clb = -h3
                    c2 = c1 + clb + t2
                    if h1 + clb <= H[n1] and c2 < cost[n2]:
                        heappush(hq, (c2, n2, 0))
                        cost[n2] = c2
                elif h3 <= H[n2]:
                    c2 = c1 + t2
                    if c2 < cost[n2]:
                        heappush(hq, (c2, n2, h3))
                        cost[n2] = c2
                else:
                    h2 = H[n2]
                    fall = h3 - h2
                    c2 = c1 + fall + t2
                    if c2 < cost[n2]:
                        heappush(hq, (c2, n2, h2))
                        cost[n2] = c2
    else:
        print(-1)

solve()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M, X = map(int, input().split())
H = [int(input()) for i in range(N)]
G = [[] for i in range(N)]
for i in range(M):
    a, b, t = map(int, input().split()); a -= 1; b -= 1
    if H[a] >= t:
        G[a].append((b, t))
    if H[b] >= t:
        G[b].append((a, t))

INF = 10**18
que = [(-X, 0)]
dist = [INF]*N
dist[0] = -X
while que:
    cost, v = heappop(que)
    if dist[v] < cost:
        continue
    for w, t in G[v]:
        d = max(cost + t, -H[w])
        if d < dist[w]:
            dist[w] = d
            heappush(que, (d, w))
if dist[N-1] == INF:
    print(-1)
else:
    print((X + dist[N-1]) + (H[N-1] + dist[N-1]))

Submission status: Accepted

Solution code:
import sys
import heapq as q

sys.setrecursionlimit(10 ** 8)

n, m, x = [int(i) for i in input().split()]
H = [0] + [int(input()) for i in range(n)]
A = [[int(i) for i in input().split()] for j in range(m)]

INF = 10 ** 16

Q = []
path = [[] for i in range(n+1)]
used = [False] * (n+1)

def bfs():
    q.heappush(Q, (0, 1, x)) #(cost, node, high)
    while Q:
        cost, node, h = q.heappop(Q)
        if node == n:
            if h == H[n]:
                return cost
            q.heappush(Q, (cost+H[n]-h, n, H[n]))
            continue
        if used[node]: continue
        used[node] = True
        for a, t in path[node]:
            if 0 <= h - t <= H[a]:
                q.heappush(Q, (cost+t, a, h-t))
            elif h - t > H[a]:
                q.heappush(Q, (cost+h-H[a], a, H[a]))
            elif H[node] - t >= 0:
                q.heappush(Q, (cost+t-h+t, a, 0))

    return -1
        

for a, b, t in A:
    path[a].append((b, t))
    path[b].append((a, t))

print(bfs())

Submission status: Runtime Error

Solution code:
import sys

f = sys.stdin

n,m,x = map(int,f.readline().split())
h = [None] + [int(f.readline()) for _ in range(n)]
tuple_abt = [tuple(map(int, line.split())) for line in f]

dict_abt = {}
for ai,bi,ti in tuple_abt:
    try:
        if ti <= h[ai]:
            dict_abt[ai][bi] = ti
    except KeyError:
        dict_abt[ai] = {bi:ti}
    try:
        if ti <= h[bi]:
            dict_abt[bi][ai] = ti
    except KeyError:
        dict_abt[bi] = {ai:ti}

class Tree:
    def __init__(self, t, h, jump_t=0, next_h=0):
        if jump_t:
            t += jump_t
            h -= jump_t
            if h < 0:# 登って辻褄を合わせる
                t += -h
                h = 0
            if next_h < h:# 降りて辻褄を合わせる
                t += h - next_h
                h = next_h
        self.t = t
        self.h = h
        self.d = t - h #基本的に高い位置の方が早い為

d = [None] * (n + 1)
d[1] = Tree(0, x)
q = [(d[1].d, 1)] # (d(v), v)
while len(q):
    _, u = q.pop() #コストが最小の木を取得
    if u not in dict_abt:
        continue
    for v, t in dict_abt[u].items():
        dv = Tree(d[u].t, d[u].h, t, h[v])
        if d[v] == None or d[v].d > dv.d:
            d[v] = dv
            q.append((d[v].d, v))
if d[-1]:
    print(d[-1].t + h[-1] - d[-1].h)
else:
    print(-1)