oj.uz

Submission #931542

# Submission time Handle Problem Language Result Execution time Memory
931542 2024-02-22T03:48:01 Z tfgs Commuter Pass (JOI18_commuter_pass) PyPy 3
0 / 100
 2000 ms 175412 KB 
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.0

# Verdict Execution time Memory Grader output
1 Correct 1525 ms 89740 KB Output is correct
2 Execution timed out 2067 ms 175412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1669 ms 138920 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 28284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1525 ms 89740 KB Output is correct
2 Execution timed out 2067 ms 175412 KB Time limit exceeded
3 Halted 0 ms 0 KB -