結果

問題 No.1612 I hate Construct a Palindrome
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:41:34
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,242 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 371,088 KB
最終ジャッジ日時 2025-06-12 16:41:51
合計ジャッジ時間 15,862 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 3 WA * 9 TLE * 3 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    n, m = map(int, sys.stdin.readline().split())
    edges = []
    adj = [[] for _ in range(n + 1)]  # 1-based
    for idx in range(1, m + 1):
        a, b, c = sys.stdin.readline().split()
        a = int(a)
        b = int(b)
        edges.append((a, b, c))
        adj[a].append((b, c, idx))
        adj[b].append((a, c, idx))

    # BFS initialization
    visited = dict()
    queue = deque()

    # Initial states: all edges from 1
    for edge_info in adj[1]:
        v, c, idx = edge_info
        state = (v, c, c)
        if state not in visited:
            visited[state] = (None, None, None, idx)  # parent state and edge index
            queue.append((v, c, c))

    found = False
    result_path = None

    while queue:
        u, first, last = queue.popleft()
        if u == n and first != last:
            # Reconstruct the path
            current_state = (u, first, last)
            path = []
            while True:
                if current_state not in visited:
                    break
                parent_info = visited[current_state]
                prev_u, prev_first, prev_last, edge_idx = parent_info
                if edge_idx is not None:
                    path.append(edge_idx)
                if prev_u is None:
                    break
                current_state = (prev_u, prev_first, prev_last)
            # Reverse to get the correct order
            path.reverse()
            # Now, we need to ensure that the path is valid, i.e., the edge indices correspond to the edges taken
            # Also, the first edge is the one from 1, and the rest follow
            # Output
            print(len(path))
            for e in path:
                print(e)
            found = True
            break
        else:
            # Explore all adjacent edges
            for edge_info in adj[u]:
                v, c, idx = edge_info
                new_state = (v, first, c)
                if new_state not in visited:
                    visited[new_state] = (u, first, last, idx)
                    queue.append(new_state)

    if not found:
        print(-1)

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