結果

問題 No.1190 Points
ユーザー lam6er
提出日時 2025-03-31 17:39:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,551 bytes
コンパイル時間 473 ms
コンパイル使用メモリ 82,920 KB
実行使用メモリ 114,964 KB
最終ジャッジ日時 2025-03-31 17:40:18
合計ジャッジ時間 7,340 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx]); idx += 1
    m = int(input[idx]); idx += 1
    p = int(input[idx]); idx += 1

    s = int(input[idx]); idx += 1
    g = int(input[idx]); idx += 1

    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(input[idx]); idx += 1
        v = int(input[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)

    def compute_bfs(start, adj_list):
        inf = float('inf')
        n_nodes = len(adj_list) - 1  # adj is 1-based
        d = [inf] * (n_nodes + 1)
        color = [-1] * (n_nodes + 1)
        d[start] = 0
        color[start] = 0
        queue = deque([start])
        component_nodes = [start]
        visited = [False] * (n_nodes + 1)
        visited[start] = True
        is_bipart = True

        while queue:
            u = queue.popleft()
            for v in adj_list[u]:
                if not visited[v]:
                    visited[v] = True
                    d[v] = d[u] + 1
                    color[v] = 1 - color[u]
                    queue.append(v)
                    component_nodes.append(v)
                else:
                    if color[v] != 1 - color[u]:
                        is_bipart = False

        bipart = [False] * (n_nodes + 1)
        for node in component_nodes:
            bipart[node] = is_bipart
        return d, bipart

    d_s, bipart_s = compute_bfs(s, adj)
    d_g, bipart_g = compute_bfs(g, adj)

    # Check if there's at least one valid path for S to G
    valid = False
    if d_s[g] != float('inf'):
        sum_d = d_s[g] + d_g[g]
        if sum_d <= p:
            rem = p - sum_d
            if rem >= 0:
                if bipart_s[g] and bipart_g[g]:
                    if rem % 2 == 0:
                        valid = True
                else:
                    valid = True

    if not valid:
        print(-1)
        return

    res = []
    for u in range(1, n + 1):
        if d_s[u] == float('inf') or d_g[u] == float('inf'):
            continue
        sum_du = d_s[u] + d_g[u]
        if sum_du > p:
            continue
        rem = p - sum_du
        if rem < 0:
            continue
        # Check bipart conditions
        if bipart_s[u] and bipart_g[u]:
            if rem % 2 != 0:
                continue
        res.append(u)

    if not res:
        print(-1)
    else:
        res.sort()
        print(len(res))
        for x in res:
            print(x)

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