結果

問題 No.1612 I hate Construct a Palindrome
ユーザー gew1fw
提出日時 2025-06-12 21:21:39
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,301 bytes
コンパイル時間 450 ms
コンパイル使用メモリ 81,904 KB
実行使用メモリ 324,912 KB
最終ジャッジ日時 2025-06-12 21:24:17
合計ジャッジ時間 16,740 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 WA * 10 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

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

    # BFS to track (current node, first_char, last_char)
    # visited[node] is a dictionary mapping (fc, lc) to (edge_id, previous node, previous fc, previous lc)
    visited = [dict() for _ in range(n + 1)]
    queue = deque()

    # Initialize with all edges from node 1
    for v, c, eid in edges[1]:
        fc = c
        lc = c
        if (fc, lc) not in visited[v]:
            visited[v][(fc, lc)] = (eid, 1, None, None)
            queue.append((v, fc, lc))

    found = False
    answer = None

    while queue:
        u, current_fc, current_lc = queue.popleft()
        if u == n:
            if current_fc != current_lc:
                # Reconstruct the path
                path = []
                current_node = u
                fc, lc = current_fc, current_lc
                while True:
                    entry = visited[current_node].get((fc, lc), None)
                    if entry is None:
                        break
                    eid, prev_node, prev_fc, prev_lc = entry
                    path.append(eid)
                    if prev_node == 1 and prev_fc is None and prev_lc is None:
                        break
                    current_node = prev_node
                    fc, lc = prev_fc, prev_lc
                path.reverse()
                if len(path) <= 2 * n:
                    answer = path
                    found = True
                break
            continue

        for v, c, eid in edges[u]:
            new_fc = current_fc
            new_lc = c
            if (new_fc, new_lc) not in visited[v]:
                visited[v][(new_fc, new_lc)] = (eid, u, current_fc, current_lc)
                queue.append((v, new_fc, new_lc))
        if found:
            break

    if found:
        print(len(answer))
        for eid in answer:
            print(eid)
    else:
        print(-1)

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