結果

問題 No.1612 I hate Construct a Palindrome
コンテスト
ユーザー LyricalMaestro
提出日時 2025-05-04 15:10:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 640 ms / 2,000 ms
コード長 4,309 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 162,836 KB
最終ジャッジ日時 2025-05-04 15:11:02
合計ジャッジ時間 11,028 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1612

from collections import deque

def find_path(N, next_nodes, start, goal):
    prev = [-2] * N
    prev[start] = (-1, -1)

    queue = deque()
    queue.append(start)
    while len(queue) > 0:
        v = queue.popleft()
        for u, index, _ in next_nodes[v]:
            if prev[u] == -2:
                prev[u] = (v, index)
                queue.append(u)
    
    v = goal
    path = []
    while v != start:
        v, index = prev[v]
        path.append(index)
    path.reverse()
    return path


def find_path2(N, next_nodes, start):
    dists = [float("inf")] * N
    prev = [-2] * N
    prev[start] = (-1, -1)
    dists[start] = 0

    queue = deque()
    queue.append(start)
    while len(queue) > 0:
        v = queue.popleft()
        for u, index, _ in next_nodes[v]:
            if prev[u] == -2:
                prev[u] = (v, index)
                dists[u] = dists[v] + 1
                queue.append(u)

    return dists, prev

def main():
    N, M = map(int, input().split())
    words = set()
    next_nodes = [[] for _ in range(N)]
    edges = []
    for index in range(M):
        u, v, w = input().split()
        u = int(u) - 1
        v = int(v) - 1
        next_nodes[u].append((v, index, w))
        next_nodes[v].append((u, index, w))
    
        words.add(w)
        edges.append((u, v, w))

    if len(words) == 1:
        print(-1)
        return
    
    def get_targets(f_words, t_words):
        for f in f_words:
            for t in t_words:
                if f != t:
                     return f, t
        return None, None

    f_words = set()
    t_words = set()
    for _, _, w in next_nodes[0]:
        f_words.add(w)
    for _, _, w in next_nodes[N - 1]:
        t_words.add(w)

    target_f, target_t = get_targets(f_words, t_words)
    if target_t is None:
        # 特殊な解き方
        target_t = list(f_words)[0]

        new_next_nodes = [[] for _ in range(N)]
        for index in range(M):
            if edges[index][2] == target_t:        
                u, v, w = edges[index]
                new_next_nodes[u].append((v, index, w))
                new_next_nodes[v].append((u, index, w))
    
        dists, prev = find_path2(N, new_next_nodes, 0)
        target_i = -1
        target_v = -1
        target_u = -1
        min_dist = float("inf")
        for i in range(N):
            if min_dist > dists[i]:
                for v, index, w in next_nodes[i]:
                    if w != target_t:
                        min_dist = dists[i]
                        target_i = index
                        target_u= i
                        target_v = v
        # 初回のパス作り
        v = target_u
        from_path = []
        while v != 0:
            v, index = prev[v]
            from_path.append(index)
        from_path.reverse()
        from_path.append(target_i)

        # ゴール側の対応
        path = find_path(N, next_nodes, target_v, N - 1)
        answer = from_path + path

        # 回文チェック
        is_ok = True
        left = 0
        right = len(answer) - 1
        while left < right:
            l = edges[answer[left] ][2] 
            r = edges[answer[right]][2]
            if l != r:
                is_ok = False
                break
            left += 1
            right -= 1

        if is_ok:
            _, index, _ = next_nodes[N - 1][0]      
            answer.append(index)
            answer.append(index)

        print(len(answer))
        for ans in answer:
            print(ans + 1)

    else:
        # 最初だけ異なってあとは最短経路
        f_array = []
        next_v = -1
        for v, index, w in next_nodes[0]:
            if w == target_f:
                f_array.append(index)
                next_v = v
                break
        
        t_array = []
        next_v2 = -1
        for v, index, w in next_nodes[N - 1]:
            if w == target_t:
                t_array.append(index)
                next_v2 = v
                break

        path = find_path(N, next_nodes, next_v, next_v2)
        answer = f_array + path + t_array

        print(len(answer))
        for ans in answer:
            print(ans + 1)







        

        

        







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