結果

問題 No.1776 Love Triangle 2 (Hard)
ユーザー lam6er
提出日時 2025-04-16 00:17:20
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,957 bytes
コンパイル時間 529 ms
コンパイル使用メモリ 81,536 KB
実行使用メモリ 87,904 KB
最終ジャッジ日時 2025-04-16 00:19:00
合計ジャッジ時間 33,239 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 45 WA * 131
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
import heapq

def main():
    n, m = map(int, input().split())
    X, Y, Z = map(int, input().split())
    friends = [set() for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, input().split())
        friends[a].add(b)
        friends[b].add(a)
    
    # Build complement graph
    complement = [[] 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]:
                complement[u].append(v)
    
    # BFS for minimal k
    visited = {}
    queue = deque()
    initial_mask = 0
    queue.append((X, initial_mask, 0))
    visited[(X, initial_mask)] = 0
    found_k = False
    answer_k = -1
    
    while queue:
        current, mask, steps = queue.popleft()
        
        if current == X and mask == 3:
            answer_k = steps
            found_k = True
            break
        
        for neighbor in complement[current]:
            new_mask = mask
            if neighbor == Y:
                new_mask |= 1
            elif neighbor == Z:
                new_mask |= 2
            new_steps = steps + 1
            
            if neighbor == X:
                if new_mask == 3:
                    if (neighbor, new_mask) not in visited or new_steps < visited.get((neighbor, new_mask), float('inf')):
                        visited[(neighbor, new_mask)] = new_steps
                        queue.append((neighbor, new_mask, new_steps))
                        if neighbor == X and new_mask == 3:
                            answer_k = new_steps
                            found_k = True
                            queue = deque()
                            break
                continue
            
            key = (neighbor, new_mask)
            if key not in visited or new_steps < visited[key]:
                visited[key] = new_steps
                queue.append((neighbor, new_mask, new_steps))
        if found_k:
            break
    
    if not found_k:
        print(-1)
        return
    
    k = answer_k
    # BFS for lex smallest path
    heap = []
    initial_path = (X,)
    heapq.heappush(heap, (initial_path, X, 0, 0))
    visited_lex = {}
    found_lex = False
    result_path = None
    
    while heap:
        path_tuple, current, mask, steps = heapq.heappop(heap)
        path = list(path_tuple)
        
        if current == X and mask == 3 and steps == k:
            result_path = path
            found_lex = True
            break
        
        if steps >= k:
            continue
        
        neighbors = sorted(complement[current])
        for v in neighbors:
            if v == X:
                if steps + 1 == k and mask == 3:
                    new_path = path + [v]
                    result_path = new_path
                    found_lex = True
                    heap = []
                    break
                continue
            
            if v in path:
                continue
            
            new_mask = mask
            if v == Y:
                new_mask |= 1
            elif v == Z:
                new_mask |= 2
            new_steps = steps + 1
            new_path = path + [v]
            new_path_tuple = tuple(new_path)
            
            state_key = (v, new_mask, new_steps)
            if state_key in visited_lex:
                existing_path = visited_lex[state_key]
                if new_path_tuple < existing_path:
                    visited_lex[state_key] = new_path_tuple
                    heapq.heappush(heap, (new_path_tuple, v, new_mask, new_steps))
            else:
                visited_lex[state_key] = new_path_tuple
                heapq.heappush(heap, (new_path_tuple, v, new_mask, new_steps))
        if found_lex:
            break
    
    if found_lex:
        print(k)
        print(' '.join(map(str, result_path)))
    else:
        print(-1)

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