扉が一つずつ閉まる博物館

import sysfrom collections import deque data = sys.stdin.read().split()n, m = int(data[0]), int(data[1])close = [0] + [int(x) for x in data[2:2 + n]]  # close[v] = v번 전시실에 들어갈 수 있는 마지막 시각 # 인접 목록: halls[v] = v번 전시실과 복도로 이어진 전시실들(양쪽으로 다닌다)halls = [[] for _ in range(n + 1)]for i in range(m):    a, b = int(data[2 + n + 2 * i]), int(data[3 + n + 2 * i])    halls[a].append(b)    halls[b].append(a) # 너비 우선 탐색(BFS): 큐에서 꺼내는 차례가 곧 도착 시각이 이른 차례다arrive = [-1] * (n + 1)arrive[1] = 0  # 1번에는 처음부터 있으니 close[1]은 보지 않는다queue = deque([1])while queue:    u = queue.popleft()    t = arrive[u] + 1  # 이웃 전시실에 닿는 시각    for v in halls[u]:        # 처음 닿는 때가 가장 이른 때다. 그때 이미 잠겼으면 나중에 와도 잠겨 있다        if arrive[v] == -1 and t <= close[v]:            arrive[v] = t            queue.append(v) print(sum(1 for v in range(1, n + 1) if arrive[v] != -1))print(" ".join(map(str, arrive[1:])))

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];// close[v] = v번 전시실에 들어갈 수 있는 마지막 시각const close = [0];for (let v = 1; v <= n; v++) close.push(data[1 + v]); // 인접 목록: halls[v] = v번 전시실과 복도로 이어진 전시실들(양쪽으로 다닌다)const halls = Array.from({ length: n + 1 }, () => []);for (let i = 0; i < m; i++) {  const a = data[2 + n + 2 * i];  const b = data[3 + n + 2 * i];  halls[a].push(b);  halls[b].push(a);} // 너비 우선 탐색(BFS): 큐에서 꺼내는 차례가 곧 도착 시각이 이른 차례다const arrive = new Array(n + 1).fill(-1);arrive[1] = 0; // 1번에는 처음부터 있으니 close[1]은 보지 않는다const queue = [1];// shift()는 뒤의 것을 모두 당겨서 느리다. 머리 번호 head를 옮긴다for (let head = 0; head < queue.length; head++) {  const u = queue[head];  const t = arrive[u] + 1; // 이웃 전시실에 닿는 시각  for (const v of halls[u]) {    // 처음 닿는 때가 가장 이른 때다. 그때 이미 잠겼으면 나중에 와도 잠겨 있다    if (arrive[v] === -1 && t <= close[v]) {      arrive[v] = t;      queue.push(v);    }  }} console.log(queue.length); // 큐에 한 번씩 들어간 전시실이 곧 들어갈 수 있는 전시실이다console.log(arrive.slice(1).join(" "));

import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];// close[v] = v번 전시실에 들어갈 수 있는 마지막 시각const close: number[] = [0];for (let v = 1; v <= n; v++) close.push(data[1 + v]); // 인접 목록: halls[v] = v번 전시실과 복도로 이어진 전시실들(양쪽으로 다닌다)const halls: number[][] = Array.from({ length: n + 1 }, (): number[] => []);for (let i = 0; i < m; i++) {  const a = data[2 + n + 2 * i];  const b = data[3 + n + 2 * i];  halls[a].push(b);  halls[b].push(a);} // 너비 우선 탐색(BFS): 큐에서 꺼내는 차례가 곧 도착 시각이 이른 차례다const arrive: number[] = new Array<number>(n + 1).fill(-1);arrive[1] = 0; // 1번에는 처음부터 있으니 close[1]은 보지 않는다const queue: number[] = [1];// shift()는 뒤의 것을 모두 당겨서 느리다. 머리 번호 head를 옮긴다for (let head = 0; head < queue.length; head++) {  const u = queue[head];  const t = arrive[u] + 1; // 이웃 전시실에 닿는 시각  for (const v of halls[u]) {    // 처음 닿는 때가 가장 이른 때다. 그때 이미 잠겼으면 나중에 와도 잠겨 있다    if (arrive[v] === -1 && t <= close[v]) {      arrive[v] = t;      queue.push(v);    }  }} console.log(queue.length); // 큐에 한 번씩 들어간 전시실이 곧 들어갈 수 있는 전시실이다console.log(arrive.slice(1).join(" "));

import java.io.*;import java.util.*; public class Main {    public static void main(String[] args) throws IOException {        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));        st.nextToken();        int n = (int) st.nval;        st.nextToken();        int m = (int) st.nval;        int[] close = new int[n + 1]; // close[v] = v번 전시실에 들어갈 수 있는 마지막 시각        for (int v = 1; v <= n; v++) {            st.nextToken();            close[v] = (int) st.nval;        }         // 인접 목록: halls.get(v) = v번 전시실과 복도로 이어진 전시실들(양쪽으로 다닌다)        List<List<Integer>> halls = new ArrayList<>();        for (int v = 0; v <= n; v++) halls.add(new ArrayList<>());        for (int i = 0; i < m; i++) {            st.nextToken();            int a = (int) st.nval;            st.nextToken();            int b = (int) st.nval;            halls.get(a).add(b);            halls.get(b).add(a);        }         // 너비 우선 탐색(BFS): 큐에서 꺼내는 차례가 곧 도착 시각이 이른 차례다        int[] arrive = new int[n + 1];        Arrays.fill(arrive, -1);        arrive[1] = 0; // 1번에는 처음부터 있으니 close[1]은 보지 않는다        ArrayDeque<Integer> queue = new ArrayDeque<>();        queue.add(1);        int reached = 1;        while (!queue.isEmpty()) {            int u = queue.poll();            int t = arrive[u] + 1; // 이웃 전시실에 닿는 시각            for (int v : halls.get(u)) {                // 처음 닿는 때가 가장 이른 때다. 그때 이미 잠겼으면 나중에 와도 잠겨 있다                if (arrive[v] == -1 && t <= close[v]) {                    arrive[v] = t;                    queue.add(v);                    reached++;                }            }        }         StringBuilder sb = new StringBuilder();        sb.append(reached).append('\n');        for (int v = 1; v <= n; v++) sb.append(arrive[v]).append(v < n ? ' ' : '\n');        System.out.print(sb);    }}

using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries);        int n = int.Parse(data[0]), m = int.Parse(data[1]);        var close = new int[n + 1]; // close[v] = v번 전시실에 들어갈 수 있는 마지막 시각        for (int v = 1; v <= n; v++) close[v] = int.Parse(data[1 + v]);         // 인접 목록: halls[v] = v번 전시실과 복도로 이어진 전시실들(양쪽으로 다닌다)        var halls = new List<int>[n + 1];        for (int v = 0; v <= n; v++) halls[v] = new List<int>();        for (int i = 0; i < m; i++)        {            int a = int.Parse(data[2 + n + 2 * i]), b = int.Parse(data[3 + n + 2 * i]);            halls[a].Add(b);            halls[b].Add(a);        }         // 너비 우선 탐색(BFS): 큐에서 꺼내는 차례가 곧 도착 시각이 이른 차례다        var arrive = new int[n + 1];        Array.Fill(arrive, -1);        arrive[1] = 0; // 1번에는 처음부터 있으니 close[1]은 보지 않는다        var queue = new Queue<int>();        queue.Enqueue(1);        int reached = 1;        while (queue.Count > 0)        {            int u = queue.Dequeue();            int t = arrive[u] + 1; // 이웃 전시실에 닿는 시각            foreach (int v in halls[u])            {                // 처음 닿는 때가 가장 이른 때다. 그때 이미 잠겼으면 나중에 와도 잠겨 있다                if (arrive[v] == -1 && t <= close[v])                {                    arrive[v] = t;                    queue.Enqueue(v);                    reached++;                }            }        }         var sb = new StringBuilder();        sb.Append(reached).Append('\n');        for (int v = 1; v <= n; v++) sb.Append(arrive[v]).Append(v < n ? ' ' : '\n');        Console.Write(sb);    }}

#include <iostream>#include <queue>#include <vector>using namespace std; int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    int n, m;    cin >> n >> m;    vector<int> close(n + 1); // close[v] = v번 전시실에 들어갈 수 있는 마지막 시각    for (int v = 1; v <= n; v++) cin >> close[v];     // 인접 목록: halls[v] = v번 전시실과 복도로 이어진 전시실들(양쪽으로 다닌다)    vector<vector<int>> halls(n + 1);    for (int i = 0; i < m; i++) {        int a, b;        cin >> a >> b;        halls[a].push_back(b);        halls[b].push_back(a);    }     // 너비 우선 탐색(BFS): 큐에서 꺼내는 차례가 곧 도착 시각이 이른 차례다    vector<int> arrive(n + 1, -1);    arrive[1] = 0; // 1번에는 처음부터 있으니 close[1]은 보지 않는다    queue<int> q;    q.push(1);    int reached = 1;    while (!q.empty()) {        int u = q.front();        q.pop();        int t = arrive[u] + 1; // 이웃 전시실에 닿는 시각        for (int v : halls[u]) {            // 처음 닿는 때가 가장 이른 때다. 그때 이미 잠겼으면 나중에 와도 잠겨 있다            if (arrive[v] == -1 && t <= close[v]) {                arrive[v] = t;                q.push(v);                reached++;            }        }    }     cout << reached << '\n';    for (int v = 1; v <= n; v++) cout << arrive[v] << (v < n ? ' ' : '\n');    return 0;}

#include <stdio.h>#include <stdlib.h> int main(void) {    int n, m;    if (scanf("%d %d", &n, &m) != 2) return 0;    int *close = malloc((n + 1) * sizeof(int)); // close[v] = v번 전시실에 들어갈 수 있는 마지막 시각    for (int v = 1; v <= n; v++) scanf("%d", &close[v]);     // 인접 목록을 배열 셋으로: head[v]에서 시작해 next[e]로 따라가며 to[e]를 본다    // 복도 하나가 양쪽으로 다니는 길 둘이 되므로 칸이 2m개 든다    int *head = malloc((n + 1) * sizeof(int));    int *next = malloc((2 * m + 1) * sizeof(int));    int *to = malloc((2 * m + 1) * sizeof(int));    for (int v = 0; v <= n; v++) head[v] = -1;    for (int i = 0; i < m; i++) {        int a, b;        scanf("%d %d", &a, &b);        to[2 * i] = b;        next[2 * i] = head[a];        head[a] = 2 * i;        to[2 * i + 1] = a;        next[2 * i + 1] = head[b];        head[b] = 2 * i + 1;    }     // 너비 우선 탐색(BFS): 큐에서 꺼내는 차례가 곧 도착 시각이 이른 차례다    int *arrive = malloc((n + 1) * sizeof(int));    int *queue = malloc((n + 1) * sizeof(int)); // 전시실마다 한 번만 들어가니 n칸이면 된다    for (int v = 0; v <= n; v++) arrive[v] = -1;    arrive[1] = 0; // 1번에는 처음부터 있으니 close[1]은 보지 않는다    int qh = 0, qt = 0;    queue[qt++] = 1;    while (qh < qt) {        int u = queue[qh++];        int t = arrive[u] + 1; // 이웃 전시실에 닿는 시각        for (int e = head[u]; e != -1; e = next[e]) {            int v = to[e];            // 처음 닿는 때가 가장 이른 때다. 그때 이미 잠겼으면 나중에 와도 잠겨 있다            if (arrive[v] == -1 && t <= close[v]) {                arrive[v] = t;                queue[qt++] = v;            }        }    }     printf("%d\n", qt); // 큐에 한 번씩 들어간 전시실의 수    for (int v = 1; v <= n; v++) printf(v > 1 ? " %d" : "%d", arrive[v]);    printf("\n");    free(close); free(head); free(next); free(to); free(arrive); free(queue);    return 0;}

첫줄 = コンソール.数読み();n = 첫줄[0];m = 첫줄[1];// 목록은 10,000칸까지라 전시실 번호에서 1을 빼 0번부터 둔다// close[v] = v번 전시실에 들어갈 수 있는 마지막 시각close = コンソール.数読み(); // 인접 목록: halls[v] = v번 전시실과 복도로 이어진 전시실들(양쪽으로 다닌다)halls = [];繰り返す (v = 0; v < n; v++){    halls.追加([]);}繰り返す (i = 0; i < m; i++){    쌍 = コンソール.数読み();    halls[쌍[0] - 1].追加(쌍[1] - 1);    halls[쌍[1] - 1].追加(쌍[0] - 1);} // 너비 우선 탐색(BFS): 큐에서 꺼내는 차례가 곧 도착 시각이 이른 차례다arrive = 新リスト(n, -1);arrive[0] = 0; // 1번에는 처음부터 있으니 close는 보지 않는다queue = [0];// 앞에서 빼는 대신 머리 번호 head를 옮긴다head = 0;間 (head < queue.個数){    u = queue[head];    head++;    t = arrive[u] + 1; // 이웃 전시실에 닿는 시각    それぞれ (v の中 halls[u])    {        // 처음 닿는 때가 가장 이른 때다. 그때 이미 잠겼으면 나중에 와도 잠겨 있다        もし (arrive[v] == -1 && t <= close[v])        {            arrive[v] = t;            queue.追加(v);        }    }} コンソール.書く(queue.個数); // 큐에 한 번씩 들어간 전시실의 수コンソール.書く(arrive);