代码

import heapq as h

v, n, t, ne = map(int, input().split())
a = list(map(int, input().split()))
a.insert(0, 0)

# dfs+cache
cache = {}
def dfs(i, p, now):
    if i in cache:
        return cache[i]
    # print(i)
    if i == 0:
        return dfs(i + 1, p, now)
    if i == len(p):
        return 0, now
    ret = None
    if a[p[i]] > v // 2:
        ret = dfs(i + 1, p, now + a[p[i]] - v // 2)
    elif a[p[i]] < v // 2:
        if now >= v // 2 - a[p[i]]:
            ret = dfs(i + 1, p, now - (v // 2 - a[p[i]]))
        else:
            ret = v // 2 - a[p[i]] - now + dfs(i + 1, p, 0)[0], dfs(i + 1, p, 0)[1]
    else:
        ret = dfs(i + 1, p, now)
    cache[i] = ret
    return ret


e = []
for _ in range(ne):
    e.append(list(map(int, input().split())))
g = [[] for _ in range(n + 1)]
for x, y, z in e:
    g[x].append((y, z))
    g[y].append((x, z))

# dijskra+记录路径(bfs)
q = [(0, 0, [0])]
res = []
vis = [0] * (n + 1)
while q:
    tot, now, path = h.heappop(q)
    if vis[now]:
        continue
    vis[now] = 1
    for nex, val in g[now]:
        if nex == t:
            res.append((tot + val, path + [nex]))
        h.heappush(q, (val + tot, nex, path + [nex]))
#找到最小路径存放到ret
mi = 1e9
for x, y in res:
    mi = min(x, mi)
ret = []
for x, y in res:
    if x == mi:
        ret.append(y)
#最小路径中找到题目所要求的那一条
l, r = dfs(0, ret[0], 0)
rep = ret[0]
for x in ret:
    cache = {}
    nl, nr = dfs(0, x, 0)
    if nl < l:
        l, r, rep = nl, nr, x
    if nl == l and nr < r:
        l, r, rep = nl, nr, x
    # print(nl,nr,x)
ll = ''
for x in rep:
    ll += str(x) + '->'
print(l, ll[:-2], r)