結果

問題 No.1776 Love Triangle 2 (Hard)
ユーザー gew1fw
提出日時 2025-06-12 18:15:55
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,363 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 849,288 KB
最終ジャッジ日時 2025-06-12 18:16:29
合計ジャッジ時間 4,888 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 MLE * 1 -- * 171
権限があれば一括ダウンロードができます

ソースコード

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
    x = int(data[idx])
    idx += 1
    y = int(data[idx])
    idx += 1
    z = int(data[idx])
    idx += 1

    friends = [set() for _ in range(n + 1)]
    for _ in range(m):
        a = int(data[idx])
        idx += 1
        b = int(data[idx])
        idx += 1
        friends[a].add(b)
        friends[b].add(a)

    # BFS setup
    # Each state: (current, mask, prev, visited, path)
    # mask: 0b00 (no Y/Z), 0b01 (Y), 0b10 (Z), 0b11 (both)
    # visited is a set of nodes excluding X (since X is start and end)
    # path is the current path
    initial_mask = 0
    if x == y:
        initial_mask |= 1
    if x == z:
        initial_mask |= 2

    # Queue: (current, mask, prev, visited, path)
    # Using deque for BFS
    queue = deque()
    initial_visited = frozenset([x])
    initial_path = [x]
    queue.append((x, initial_mask, None, initial_visited, initial_path))

    best_k = None
    best_path = None

    visited_states = {}

    while queue:
        current, mask, prev, visited, path = queue.popleft()
        current_len = len(path)

        # Check if we can terminate at X with mask 0b11
        if current == x and current_len > 1:
            if mask == 0b11:
                k = current_len - 1
                if (best_k is None) or (k < best_k) or (k == best_k and path < best_path):
                    best_k = k
                    best_path = path.copy()
                continue

        # Generate next nodes in sorted order for lex order
        next_nodes = []
        for v in range(1, n + 1):
            if v == current:
                continue  # No self-loop
            if v in friends[current]:
                continue  # No friends adjacent
            # Check if visited (except X)
            if v != x and v in visited:
                continue
            # Check if next is X, only allowed if mask is 0b11 and path length >= 3
            if v == x:
                if mask != 0b11 or len(path) < 3:
                    continue
            next_nodes.append(v)
        next_nodes.sort()

        for v in next_nodes:
            new_mask = mask
            if v == y:
                new_mask |= 1
            if v == z:
                new_mask |= 2
            new_prev = current
            new_path = path + [v]
            new_visited = set(visited)
            if v != x:
                new_visited.add(v)
            new_visited = frozenset(new_visited)
            key = (v, new_mask, new_prev, new_visited)
            if key in visited_states:
                existing_len, existing_path = visited_states[key]
                if current_len + 1 < existing_len or (current_len + 1 == existing_len and new_path < existing_path):
                    visited_states[key] = (current_len + 1, new_path)
                    queue.append((v, new_mask, new_prev, new_visited, new_path))
            else:
                visited_states[key] = (current_len + 1, new_path)
                queue.append((v, new_mask, new_prev, new_visited, new_path))

    if best_k is not None:
        print(best_k)
        print(' '.join(map(str, best_path)))
    else:
        print(-1)

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