結果

問題 No.1776 Love Triangle 2 (Hard)
ユーザー gew1fw
提出日時 2025-06-12 15:03:32
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,587 bytes
コンパイル時間 321 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 848,840 KB
最終ジャッジ日時 2025-06-12 15:04:17
合計ジャッジ時間 7,506 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        friends[a].append(b)
        friends[b].append(a)
    
    # Precompute non-friends for each node
    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 v not in friends[u]:
                non_friends[u].append(v)
    
    # BFS initialization
    visited = dict()
    queue = deque()
    initial_visited = frozenset([X])
    initial_path = [X]
    queue.append((X, False, False, initial_visited, initial_path))
    visited[(X, False, False, initial_visited)] = True
    
    found = False
    min_k = float('inf')
    best_path = None
    
    while queue:
        current, has_y, has_z, visited_set, path = queue.popleft()
        
        # Check if we can end the cycle
        if current == X and has_y and has_z:
            if len(path) - 1 < min_k:
                min_k = len(path) - 1
                best_path = path + [X]
                found = True
            continue
        
        for next_node in non_friends[current]:
            if next_node == X:
                if has_y and has_z:
                    new_path = path + [X]
                    if len(new_path) - 1 == min_k:
                        if new_path < best_path:
                            best_path = new_path
                    elif len(new_path) - 1 < min_k:
                        min_k = len(new_path) - 1
                        best_path = new_path
                        found = True
                continue
            
            if next_node not in visited_set:
                new_has_y = has_y or (next_node == Y)
                new_has_z = has_z or (next_node == Z)
                new_visited = set(visited_set)
                new_visited.add(next_node)
                new_visited_frozen = frozenset(new_visited)
                new_path = path + [next_node]
                
                state = (next_node, new_has_y, new_has_z, new_visited_frozen)
                if state not in visited:
                    visited[state] = True
                    queue.append((next_node, new_has_y, new_has_z, new_visited_frozen, new_path))
    
    if found:
        print(min_k)
        print(' '.join(map(str, best_path)))
    else:
        print(-1)

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