結果

問題 No.1775 Love Triangle 2
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:29:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,218 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 69,396 KB
最終ジャッジ日時 2025-03-20 20:30:18
合計ジャッジ時間 7,022 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 69
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import deque

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
    X, Y, Z = X-1, Y-1, Z-1  # convert to 0-based

    friends = [set() for _ in range(N)]
    for _ in range(M):
        a = int(input[idx])-1
        b = int(input[idx+1])-1
        friends[a].add(b)
        friends[b].add(a)
        idx +=2

    # Build complementary graph (edges if not friends)
    comp = [[] for _ in range(N)]
    for u in range(N):
        for v in range(N):
            if u == v:
                continue
            if v not in friends[u]:
                comp[u].append(v)

    # Check if X, Y, Z have at least two non-friend neighbors each
    for node in [X, Y, Z]:
        if len(comp[node]) < 2:
            print(-1)
            return

    # BFS: (current node, mask (Y and Z visited))
    INF = float('inf')
    dist = [[INF]*4 for _ in range(N)]
    q = deque()
    # Start at X, not visited any, steps=0
    dist[X][0] = 0
    q.append( (X, 0, 0) )

    answer = -1

    while q:
        u, mask, steps = q.popleft()
        for v in comp[u]:
            new_mask = mask
            if v == Y:
                new_mask |= 1 << 0
            if v == Z:
                new_mask |= 1 << 1
            if v == X:
                # Check if we can form a cycle
                if new_mask == 3 and steps + 1 >=3:  # at least 3 edges (4 nodes?), but need to pass Y and Z
                    cycle_length = steps +1
                    if answer == -1 or cycle_length < answer:
                        answer = cycle_length
                continue  # don't process X as intermediate node
            new_steps = steps +1
            if new_steps >= N*4:  # prevent infinite loop (arbitrary limit)
                continue
            if dist[v][new_mask] > new_steps:
                dist[v][new_mask] = new_steps
                q.append( (v, new_mask, new_steps) )

    # answer is steps+1, which is the number of nodes in the cycle
    if answer != -1:
        print(answer)
    else:
        print(-1)

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