結果

問題 No.1612 I hate Construct a Palindrome
ユーザー lam6er
提出日時 2025-04-15 23:37:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,005 bytes
コンパイル時間 306 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 180,552 KB
最終ジャッジ日時 2025-04-15 23:39:00
合計ジャッジ時間 8,851 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 WA * 10
権限があれば一括ダウンロードができます

ソースコード

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 = []
    adj = [[] for _ in range(N+1)]  # 1-based

    for i in range(M):
        a = int(input[ptr])
        ptr += 1
        b = int(input[ptr])
        ptr += 1
        c = input[ptr]
        ptr += 1
        edges.append((a, b, c))
        adj[a].append((b, c, i+1))  # store edge index (1-based)
        adj[b].append((a, c, i+1))  # undirected

    # BFS to find shortest path from 1 to N
    prev = [None] * (N + 1)
    edge_used = [None] * (N + 1)
    q = deque()
    q.append(1)
    prev[1] = -1  # mark start

    while q:
        u = q.popleft()
        if u == N:
            break
        for (v, c, idx) in adj[u]:
            if prev[v] is None:
                prev[v] = u
                edge_used[v] = idx
                q.append(v)

    if prev[N] is None:
        print(-1)
        return

    # Reconstruct the path
    path_edges = []
    current = N
    while current != 1:
        e = edge_used[current]
        path_edges.append(e)
        current = prev[current]
    path_edges = path_edges[::-1]  # reverse to get from 1 to N

    # Check first and last characters
    first_edge_idx = path_edges[0]
    a, b, c = edges[first_edge_idx - 1]
    first_char = c

    last_edge_idx = path_edges[-1]
    a, b, c = edges[last_edge_idx - 1]
    last_char = c

    if first_char != last_char:
        print(len(path_edges))
        for e in path_edges:
            print(e)
        return

    # Look for any edge from 1 with different character
    for (v, c, idx) in adj[1]:
        if c != first_char:
            # Construct new path: 1 -> v -> 1 -> ... -> N
            new_path = [idx, idx] + path_edges
            print(len(new_path))
            for e in new_path:
                print(e)
            return

    # No such edge found
    print(-1)

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