結果

問題 No.1612 I hate Construct a Palindrome
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:40:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,959 bytes
コンパイル時間 417 ms
コンパイル使用メモリ 82,732 KB
実行使用メモリ 381,332 KB
最終ジャッジ日時 2025-04-15 23:42:59
合計ジャッジ時間 19,058 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 WA * 10 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx])
    idx += 1
    m = int(data[idx])
    idx += 1
    
    edges = [[] for _ in range(n + 1)]
    for i in range(m):
        a = int(data[idx])
        idx += 1
        b = int(data[idx])
        idx += 1
        c = data[idx]
        idx += 1
        edges[a].append((b, c, i + 1))
        edges[b].append((a, c, i + 1))
    
    # BFS to find a path where first and last characters are different
    visited = {}
    queue = deque()
    initial_state = (1, None, None)
    visited[initial_state] = (None, None, None, None)
    queue.append(initial_state)
    found = False
    result = None
    
    while queue:
        u, first, last = queue.popleft()
        if u == n:
            if first != last:
                # Reconstruct path
                path = []
                current_state = (u, first, last)
                while True:
                    prev_info = visited.get(current_state)
                    if prev_info is None:
                        break
                    prev_node, prev_first, prev_last, edge_id = prev_info
                    if edge_id is not None:
                        path.append(edge_id)
                    current_state = (prev_node, prev_first, prev_last)
                path.reverse()
                print(len(path))
                for edge in path:
                    print(edge)
                found = True
                break
            continue
        
        for v, c, edge_id in edges[u]:
            new_first = first if first is not None else c
            new_last = c
            new_state = (v, new_first, new_last)
            if new_state not in visited:
                visited[new_state] = (u, first, last, edge_id)
                queue.append(new_state)
    
    if not found:
        print(-1)

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