結果

問題 No.1612 I hate Construct a Palindrome
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:24:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,959 bytes
コンパイル時間 398 ms
コンパイル使用メモリ 81,860 KB
実行使用メモリ 387,992 KB
最終ジャッジ日時 2025-04-16 16:25:38
合計ジャッジ時間 18,355 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 WA * 10 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

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