結果

問題 No.1775 Love Triangle 2
ユーザー lam6er
提出日時 2025-03-31 17:37:26
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,703 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 676,700 KB
最終ジャッジ日時 2025-03-31 17:38:21
合計ジャッジ時間 10,147 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 MLE * 1 -- * 85
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
import sys

def main():
    input = sys.stdin.read().split()
    idx = 0
    n, m = int(input[idx]), int(input[idx+1])
    idx +=2
    x, y, z = int(input[idx]), int(input[idx+1]), int(input[idx+2])
    idx +=3
    
    friends = set()
    for _ in range(m):
        a, b = int(input[idx]), int(input[idx+1])
        friends.add((a, b))
        friends.add((b, a))
        idx +=2
    
    # Build complement graph
    complement = [[] for _ in range(n+1)]  # 1-based
    for u in range(1, n+1):
        for v in range(1, n+1):
            if u != v and (u, v) not in friends:
                complement[u].append(v)
    
    min_length = float('inf')
    start_nodes = [x, y, z]
    trio_nodes = {x, y, z}
    
    for start in start_nodes:
        # Initialize mask based on the starting node
        initial_mask = 0
        if start == x:
            initial_mask = 1 << 0
        elif start == y:
            initial_mask = 1 << 1
        else:
            initial_mask = 1 << 2
        
        initial_visited = 1 << (start - 1)
        
        q = deque()
        q.append( (start, initial_mask, initial_visited) )
        visited_states = set()
        visited_states.add( (start, initial_mask, initial_visited) )
        
        found = False
        
        while q:
            current, mask, visited = q.popleft()
            
            for neighbor in complement[current]:
                if neighbor == start:
                    if mask == 0b111:
                        cycle_length = bin(visited).count('1')
                        if cycle_length < min_length:
                            min_length = cycle_length
                            found = True
                    continue  # Don't process further if it's the start node but mask not 7
                
                if not (visited & (1 << (neighbor - 1))):
                    new_mask = mask
                    if neighbor == x:
                        new_mask |= 1 << 0
                    elif neighbor == y:
                        new_mask |= 1 << 1
                    elif neighbor == z:
                        new_mask |= 1 << 2
                    
                    new_visited = visited | (1 << (neighbor - 1))
                    state = (neighbor, new_mask, new_visited)
                    
                    if state not in visited_states:
                        visited_states.add(state)
                        q.append(state)
        
        if found:
            break  # Since BFS returns the shortest for this start node
    
    if min_length != float('inf'):
        print(min_length)
    else:
        print(-1)

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