Submission #931542

#	Time	Username	Problem	Language	Result	Execution time	Memory
931542		tfgs	Commuter Pass (JOI18_commuter_pass)	Pypy 3	0 / 100	2074 ms	175412 KiB

commuter_pass

from heapq import *

def solve():
    n, m = map(int, input().split())
    s, t = map(int, input().split())
    u, v = map(int, input().split())
    s -= 1
    t -= 1
    u -= 1
    v -= 1

    g = [[] for i in range(n)]
    rev = [[] for i in range(n)]
    dag = [[] for i in range(n)]
    for _ in range(m):
        a, b, c = map(int, (input().split()))
        a -= 1
        b -= 1
        g[a].append((c, b))
        g[b].append((c, a))

    def dijkstra(src):
        dist = [float('inf')]*n
        dist[src]=0
        q=[]
        heappush(q, (0, src))
        while q:
            d,u = heappop(q)
            for w,v in g[u]:
                if d+w<dist[v]:
                    dist[v]=d+w
                    heappush(q,(dist[v],v))
        return dist
        
    du = dijkstra(u)
    dv = dijkstra(v)
    ans = du[v]

    dist = [float('inf')]*n
    q = []
    heappush(q,(0,s))
    dist[s] = 0
    while q:
        d, u = heappop(q)
        for w,v in g[u]:
            if d+w<dist[v]:
                dist[v]=d+w
                heappush(q,(dist[v],v))
                rev[v] = []
            if d+w==dist[v]:
                rev[v].append(u)
    for u,vs in enumerate(rev):
        for v in vs:
            dag[v].append(u)

    dpB = [float('inf')]*n
    dpF = [float('inf')]*n
    def dfs(i):
        if (len(rev[i])):
            dpB[i] = min(dpB[j] for j in rev[i])
        dpB[i] = min(dpB[i], dv[i])
        for j in dag[i]:
            dfs(j)
    dfs(s)

    in_dag = []
    def dfs2(i):
        in_dag.append(i)
        if (len(dag[i])):
            dpF[i] = min(dpF[j] for j in dag[i])
        dpF[i] = min(dpF[i], dv[i])
        for j in rev[i]:
            dfs2(j)
    dfs2(t)

    for i in in_dag:
        ans = min(ans, du[i]+min(dpF[i], dpB[i]))

    print(ans)


solve()

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45