結果

問題 No.1212 Second Path
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:38:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,382 bytes
コンパイル時間 354 ms
コンパイル使用メモリ 81,988 KB
実行使用メモリ 302,884 KB
最終ジャッジ日時 2025-06-12 19:39:25
合計ジャッジ時間 11,760 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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)]  # nodes are 1-based
    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) )
        if u > v:
            u, v = v, u
        edges[(u, v)] = w

    for u in range(1, N+1):
        adj[u].sort(key=lambda x: x[1])

    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) )

    def bfs_path(start, end):
        visited = [False]*(N+1)
        parent = {}
        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 = []
        u = end
        while u is not None:
            path.append(u)
            u = parent[u]
        path.reverse()
        return path

    for x, y in queries:
        path = bfs_path(x, y)
        if not path:
            print(0)
            continue
        S = 0
        edge_set = set()
        path_edges = []
        for i in range(len(path)-1):
            u = path[i]
            v = path[i+1]
            if u > v:
                u, v = v, u
            edge_set.add( (u, v) )
            S += edges[(u, v)]
        min_branch = None
        for u in path:
            for v, w in adj[u]:
                a, b = u, v
                if a > b:
                    a, b = b, a
                if (a, b) not in edge_set:
                    if min_branch is None or w < min_branch:
                        min_branch = w
                    break  # since adj[u] is sorted, first valid is minimal
        if min_branch is not None:
            print(S + 2 * min_branch)
        else:
            print(-1)

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