結果

問題 No.1212 Second Path
ユーザー gew1fw
提出日時 2025-06-12 16:33:58
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,298 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 430,360 KB
最終ジャッジ日時 2025-06-12 16:34:31
合計ジャッジ時間 10,503 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read
    data = input().split()
    idx = 0

    N = int(data[idx])
    idx +=1

    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u = int(data[idx])
        v = int(data[idx+1])
        w = int(data[idx+2])
        idx +=3
        edges[u].append((v, w))
        edges[v].append((u, w))

    Q = int(data[idx])
    idx +=1
    queries = []
    for _ in range(Q):
        x = int(data[idx])
        y = int(data[idx+1])
        idx +=2
        queries.append((x, y))

    def find_path(x, y):
        visited = [False] * (N+1)
        parent = [None] * (N+1)
        q = deque()
        q.append(x)
        visited[x] = True
        while q:
            u = q.popleft()
            if u == y:
                break
            for v, w in edges[u]:
                if not visited[v]:
                    visited[v] = True
                    parent[v] = (u, w)
                    q.append(v)
        if parent[y] is None:
            return None
        path = []
        current = y
        while current != x:
            u, w = parent[current]
            path.append((u, current, w))
            current = u
        path.reverse()
        nodes = set()
        node_path = []
        current = x
        nodes.add(current)
        node_path.append(current)
        for u, v, w in path:
            nodes.add(v)
            node_path.append(v)
            current = v
        edge_set = set()
        for u, v, w in path:
            edge_set.add((u, v, w))
            edge_set.add((v, u, w))
        return (node_path, path, edge_set)

    for x, y in queries:
        res = find_path(x, y)
        if res is None:
            print(-1)
            continue
        node_path, path, edge_set = res
        S = sum(w for _, _, w in path)
        min_m = None
        nodes_in_path = set(node_path)
        for u in nodes_in_path:
            for v, w in edges[u]:
                if (u, v, w) not in edge_set and (v, u, w) not in edge_set:
                    if min_m is None or w < min_m:
                        min_m = w
        if min_m is not None:
            print(S + 2 * min_m)
        else:
            print(-1)

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