結果

問題 No.1612 I hate Construct a Palindrome
ユーザー lam6er
提出日時 2025-04-15 23:39:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,356 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 345,436 KB
最終ジャッジ日時 2025-04-15 23:40:39
合計ジャッジ時間 20,852 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 WA * 9 TLE * 5 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1

    edges = [[] for _ in range(N + 1)]
    all_chars = set()

    for i in range(M):
        a = int(input[ptr])
        ptr += 1
        b = int(input[ptr])
        ptr += 1
        c = input[ptr]
        ptr += 1
        edges[a].append((b, c, i + 1))
        edges[b].append((a, c, i + 1))
        all_chars.add(c)

    if len(all_chars) == 1:
        print(-1)
        return

    visited = {}
    queue = deque()
    queue.append((1, None))
    visited[(1, None)] = (None, None, None)

    while queue:
        u, fc = queue.popleft()
        for v, c, idx in edges[u]:
            new_fc = fc
            if fc is None:
                new_fc = c
            key = (v, new_fc)
            if key not in visited:
                visited[key] = (u, fc, idx)
                queue.append(key)

    for u in range(1, N + 1):
        for v, c, idx in edges[u]:
            if v == N:
                current_u = u
                target_c = c
                found = False
                for key in visited:
                    if key[0] == current_u and key[1] is not None and key[1] != target_c:
                        fc_u = key[1]
                        path = []
                        current_node, current_fc = current_u, key[1]
                        edge_list = []
                        while True:
                            parent_info = visited.get((current_node, current_fc), None)
                            if parent_info is None:
                                break
                            parent_node, parent_fc, edge_idx = parent_info
                            if edge_idx is None:
                                break
                            edge_list.append(edge_idx)
                            current_node, current_fc = parent_node, parent_fc
                        edge_list.reverse()
                        edge_list.append(idx)
                        if len(edge_list) > 2 * N:
                            continue
                        print(len(edge_list))
                        for e in edge_list:
                            print(e)
                        return

    print(-1)

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