結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    n, m = map(int, sys.stdin.readline().split())
    x, y, z = map(int, sys.stdin.readline().split())
    friends = set()
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        friends.add((a, b))
        friends.add((b, a))
    
    # Build non-friend adjacency list
    non_friends = [[] for _ in range(n+1)]
    for u in range(1, n+1):
        for v in range(1, n+1):
            if u != v and (u, v) not in friends:
                non_friends[u].append(v)
        non_friends[u].sort()  # Ensure lex order
    
    required = {x: 1, y: 2, z: 4}
    target_mask = 7  # 1 (X) | 2 (Y) | 4 (Z) = 7

    # BFS initialization
    queue = deque()
    initial_path = [x]
    initial_visited = frozenset([x])
    queue.append((x, 1, initial_path, initial_visited))
    
    best = {}
    best_key = (x, 1, initial_visited)
    best[best_key] = (0, initial_path)
    
    answer_k = None
    answer_path = None
    
    while queue:
        current_node, mask, path, visited = queue.popleft()
        current_len = len(path) - 1
        
        # Check if we've found a valid cycle
        if current_node == x and mask == target_mask and len(path) >= 4:
            # Check if the last step is valid (not friends)
            prev_node = path[-2]
            if (prev_node, x) not in friends:
                if answer_k is None or current_len < answer_k or (current_len == answer_k and path < answer_path):
                    answer_k = current_len
                    answer_path = path.copy() + [x]
                    # Early exit if lex smallest is found first
                    break
        
        # Generate next states
        for next_node in non_friends[current_node]:
            new_visited = set(visited)
            if next_node == x:
                if mask == target_mask and (current_node, x) not in friends:
                    new_path = path + [x]
                    new_len = current_len + 1
                    if (answer_k is None or new_len < answer_k) or (new_len == answer_k and new_path < answer_path):
                        answer_k = new_len
                        answer_path = new_path.copy()
                        # Early exit
                        queue = deque()
                        break
                continue
            
            if next_node in visited:
                continue
            
            new_mask = mask
            if next_node in required:
                new_mask |= required[next_node]
            
            new_visited_set = set(visited)
            new_visited_set.add(next_node)
            new_visited_frozen = frozenset(new_visited_set)
            new_path = path + [next_node]
            new_len = current_len + 1
            key = (next_node, new_mask, new_visited_frozen)
            
            if key not in best or (new_len < best[key][0]) or (new_len == best[key][0] and new_path < best[key][1]):
                best[key] = (new_len, new_path)
                queue.append((next_node, new_mask, new_path, new_visited_frozen))
    
    if answer_k is not None:
        print(answer_k)
        print(' '.join(map(str, answer_path)))
    else:
        print(-1)

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