結果

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

ソースコード

diff #
raw source code 

import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.read
data = input().split()

def main():
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u = int(data[ptr])
        v = int(data[ptr+1])
        w = int(data[ptr+2])
        ptr +=3
        edges[u].append( (v, w) )
        edges[v].append( (u, w) )
    
    from collections import deque
    def bfs(start, end):
        visited = [False]*(N+1)
        q = deque()
        q.append( (start, 0) )
        visited[start] = True
        parent = [-1]*(N+1)
        while q:
            u, dist = q.popleft()
            if u == end:
                break
            for v, w in edges[u]:
                if not visited[v]:
                    visited[v] = True
                    parent[v] = u
                    q.append( (v, dist + w) )
        if not visited[end]:
            return -1, []
        path = []
        node = end
        while node != start:
            path.append(node)
            node = parent[node]
        path.append(start)
        path = path[::-1]
        total = 0
        for i in range(len(path)-1):
            u = path[i]
            v = path[i+1]
            for nei, w in edges[u]:
                if nei == v:
                    total += w
                    break
        return total, path
    
    Q = int(data[ptr])
    ptr +=1
    for _ in range(Q):
        x = int(data[ptr])
        y = int(data[ptr+1])
        ptr +=2
        d, path = bfs(x, y)
        if d == -1:
            print(-1)
            continue
        nodes = path
        min_e = float('inf')
        for u in nodes:
            for v, w in edges[u]:
                if v not in nodes:
                    min_e = min(min_e, w)
        if min_e == float('inf'):
            print(-1)
        else:
            print(d + 2*min_e)

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