結果

問題 No.1212 Second Path
ユーザー gew1fw
提出日時 2025-06-12 19:33:37
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,482 bytes
コンパイル時間 409 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 153,980 KB
最終ジャッジ日時 2025-06-12 19:33:51
合計ジャッジ時間 13,207 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

sys.setrecursionlimit(1 << 25)

def main():
    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))
    
    for x, y in queries:
        if x == y:
            print(-1)
            continue
        
        visited = [False] * (N+1)
        parent = [0]*(N+1)
        distance = [0]*(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 edges[u]:
                if not visited[v]:
                    visited[v] = True
                    parent[v] = u
                    distance[v] = distance[u] + w
                    q.append(v)
        
        if not found:
            print(-1)
            continue
        
        d = distance[y]
        path = []
        current = y
        while current != x:
            path.append(current)
            current = parent[current]
        path.append(x)
        path = path[::-1]
        
        min_w = float('inf')
        for u in path:
            for v, w in edges[u]:
                if v == parent[u] or (u == path[-1] and v == path[-2]):
                    continue
                if v == parent[u]:
                    if u == path[0]:
                        continue
                    else:
                        if parent[u] == path[path.index(u)-1]:
                            continue
                        else:
                            pass
                else:
                    if v in path:
                        if path.index(v) == path.index(u)+1:
                            continue
                        else:
                            pass
                    else:
                        pass
                if w < min_w:
                    min_w = w
        
        if min_w == float('inf'):
            print(-1)
        else:
            print(d + 2*min_w)

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