結果

問題 No.1212 Second Path
ユーザー lam6er
提出日時 2025-04-16 00:22:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,924 bytes
コンパイル時間 364 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 294,048 KB
最終ジャッジ日時 2025-04-16 00:24:15
合計ジャッジ時間 10,588 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1

    adj = [[] for _ in range(N+1)]  # 1-based
    for _ in range(N-1):
        u = int(input[ptr])
        v = int(input[ptr+1])
        w = int(input[ptr+2])
        ptr +=3
        adj[u].append( (v, w) )
        adj[v].append( (u, w) )

    # Preprocess for each node the sorted edges by weight and min1, min2
    min1 = [ (float('inf'), None) ] * (N+1)
    min2 = [ (float('inf'), None) ] * (N+1)
    for u in range(1, N+1):
        edges = sorted(adj[u], key=lambda x: x[1])
        if len(edges) >= 1:
            min1[u] = edges[0]
        if len(edges) >= 2:
            min2[u] = edges[1]

    Q = int(input[ptr])
    ptr +=1
    for _ in range(Q):
        x = int(input[ptr])
        y = int(input[ptr+1])
        ptr +=2

        # Find path from x to y using BFS
        visited = [False]*(N+1)
        parent = [None]*(N+1)
        q = deque()
        q.append(x)
        visited[x] = True
        found = False
        while q:
            u = q.popleft()
            if u == y:
                found = True
                break
            for v, w in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    parent[v] = u
                    q.append(v)
        if not found:
            print(-1)
            continue

        # Reconstruct path
        path = []
        current = y
        while current is not None:
            path.append(current)
            current = parent[current]
        path = path[::-1]  # from x to y

        # Compute S
        S = 0
        edge_path = set()
        for i in range(len(path)-1):
            u = path[i]
            v = path[i+1]
            for (node, w) in adj[u]:
                if node == v:
                    S += w
                    edge = (u, v) if u < v else (v, u)
                    edge_path.add(edge)
                    break

        # Collect candidates
        min_candidate = float('inf')
        for i in range(len(path)):
            u = path[i]
            prev_u = path[i-1] if i > 0 else None
            next_u = path[i+1] if i < len(path)-1 else None

            # Check edges of u
            edges_on_path = set()
            if prev_u is not None:
                edges_on_path.add(prev_u)
            if next_u is not None:
                edges_on_path.add(next_u)

            # Check min1
            if min1[u][0] != float('inf'):
                v, w = min1[u]
                if v not in edges_on_path:
                    if w < min_candidate:
                        min_candidate = w
                    continue
                else:
                    # Check min2
                    if min2[u][0] != float('inf'):
                        v2, w2 = min2[u]
                        if v2 not in edges_on_path:
                            if w2 < min_candidate:
                                min_candidate = w2
                            continue
                        else:
                            # Check further edges
                            for (v3, w3) in adj[u]:
                                if v3 != prev_u and v3 != next_u:
                                    if w3 < min_candidate:
                                        min_candidate = w3
                                    break
                    else:
                        # Check all edges
                        for (v3, w3) in adj[u]:
                            if v3 != prev_u and v3 != next_u:
                                if w3 < min_candidate:
                                    min_candidate = w3
                                break

        if min_candidate != float('inf'):
            print(S + 2 * min_candidate)
        else:
            print(-1)

if __name__ == "__main__":
    main()
0