SoundHound 2018 予選 D - Saving Snuuk - いろんなことで四苦Hack（仮）

続きです。

ダイクストラな問題みたい。普通にわからんかったが。

editorial.pdfを見て実装してみる。

最後の出力が $O(N^{2})$ になってここがボトルネックになってTLEになっている。editorialにもここの処理書いてないやん。適当に検索したら、逆からやれば良いらしい。つよい。

"""
「sからiに円による支払いで移動する際の最小の金額」円と、「iからtにスヌークによる支払いで移動する際の最小金額」スヌークになる。これを最小化すれば良い。
"""
from collections import defaultdict
G1 = defaultdict(list); G2 = defaultdict(list)
N, M, S, T = map(int, input().split())
S-=1; T-=1
for i in range(M):
    f, t , v1, v2 = map(int, input().split())
    G1[f-1].append((t-1, v1))
    G1[t-1].append((f-1, v1))
    G2[f-1].append((t-1, v2))
    G2[t-1].append((f-1, v2))

import queue
push = queue.heappush
pop = queue.heappop
INF = 10**16
d1 = [INF]*N; d2 = [INF]*N

def dijkstra(s, G, d):
    q = []
    d[s] = 0
    push(q, (0, s))

    while q:
        cost, v = pop(q)
        # print(f'd[{v}] = {cost}')
        # 既に q から取り出したものの方が低い
        if d[v] < cost:
            continue
        for to, tmpcost in G[v]:
            if d[to] > d[v] + tmpcost:
                d[to] = d[v] + tmpcost
                push(q, (d[to], to))

dijkstra(S, G1, d1)
dijkstra(T, G2, d2)
"""
for i in range(N):
    ans = 0
    for j in range(i, N):
        ans = max(ans, 10**15-d1[j]-d2[j])
    print(ans)
"""
anses = [0]*N
ans = 10**15
for i in range(N):
    ans = min(ans, d1[N-1-i]+d2[N-1-i])
    anses[N-1-i]=10**15-ans
for i in range(N):
    print(anses[i])

すげ〜。今日もACした。今日は週の始まりですね。今週も頑張りましょう！！！