結果

問題 No.1212 Second Path
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:41:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,149 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 81,964 KB
実行使用メモリ 322,864 KB
最終ジャッジ日時 2025-06-12 19:41:38
合計ジャッジ時間 9,905 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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)]
    edges = {}
    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))
        edges[(u, v)] = w
        edges[(v, u)] = w

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

    # Preprocess BFS for path finding
    def bfs_path(start, end):
        parent = {}
        visited = [False]*(N+1)
        q = deque()
        q.append(start)
        visited[start] = True
        parent[start] = None
        found = False
        while q:
            u = q.popleft()
            if u == end:
                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:
            return []
        path = []
        current = end
        while current is not None:
            path.append(current)
            current = parent[current]
        path.reverse()
        return path

    for x, y in queries:
        path = bfs_path(x, y)
        if not path:
            print(-1)
            continue
        S = 0
        path_edges = set()
        for i in range(len(path)-1):
            u = path[i]
            v = path[i+1]
            if (u, v) in edges:
                path_edges.add((u, v))
                path_edges.add((v, u))
                S += edges[(u, v)]
        min_m = float('inf')
        for u in path:
            for v, w in adj[u]:
                if (u, v) not in path_edges:
                    if w < min_m:
                        min_m = w
        if min_m == float('inf'):
            print(-1)
        else:
            print(S + 2 * min_m)

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