奇数分、偶数分にだけ開く橋

import sysfrom collections import deque  def main():    data = sys.stdin.buffer.read().split()    n, m = int(data[0]), int(data[1])    shelter = [0] + [int(x) for x in data[2:2 + n]]    bridges = [[] for _ in range(n + 1)]  # bridges[u] = (이웃 섬, 종류)들    pos = 2 + n    for _ in range(m):        a, b, k = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])        pos += 3        bridges[a].append((b, k))        bridges[b].append((a, k))     # 상태 = (섬, 분의 홀짝). when[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때    when = [-1] * (2 * n + 2)    when[2 * 1 + 0] = 0    queue = deque([2])  # list.pop(0)은 뒤 칸을 모두 당겨서 느리다    while queue:        state = queue.popleft()        u, p = state // 2, state % 2        t = when[state] + 1        q = 1 - p        if shelter[u] and when[2 * u + q] == -1:  # 쉼터에서 1분 기다린다            when[2 * u + q] = t            queue.append(2 * u + q)        for v, k in bridges[u]:            # 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다            if (k == 0 or (k == 1) == (p == 1)) and when[2 * v + q] == -1:                when[2 * v + q] = t                queue.append(2 * v + q)     # 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽    first = []    for v in range(1, n + 1):        times = [x for x in (when[2 * v], when[2 * v + 1]) if x != -1]        first.append(min(times) if times else -1)    print(sum(1 for x in first if x != -1))    print(" ".join(map(str, first)))  main()

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];const shelter = [0];for (let v = 1; v <= n; v++) shelter.push(data[1 + v]); // bridges[u] = [이웃 섬, 종류]들(다리는 양쪽으로 건넌다)const bridges = Array.from({ length: n + 1 }, () => []);for (let i = 0; i < m; i++) {  const a = data[2 + n + 3 * i];  const b = data[3 + n + 3 * i];  const k = data[4 + n + 3 * i];  bridges[a].push([b, k]);  bridges[b].push([a, k]);} // 상태 = (섬, 분의 홀짝). time[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때const time = new Array(2 * n + 2).fill(-1);time[2 * 1 + 0] = 0;const queue = [2];// shift()는 뒤의 것을 모두 당겨서 느리다. 머리 번호 head를 옮긴다for (let head = 0; head < queue.length; head++) {  const u = queue[head] >> 1;  const p = queue[head] & 1;  const t = time[queue[head]];  const visit = (v) => {    const s = 2 * v + (1 - p);    if (time[s] === -1) {      time[s] = t + 1;      queue.push(s);    }  };  if (shelter[u] === 1) visit(u); // 쉼터에서 1분 기다린다  for (const [v, k] of bridges[u]) {    // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다    if (k === 0 || (k === 1) === (p === 1)) visit(v);  }} const first = [];let reached = 0;for (let v = 1; v <= n; v++) {  const even = time[2 * v];  const odd = time[2 * v + 1];  // 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽  const best = even === -1 ? odd : odd === -1 ? even : Math.min(even, odd);  if (best !== -1) reached++;  first.push(best);}console.log(reached);console.log(first.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];const shelter: number[] = [0];for (let v = 1; v <= n; v++) shelter.push(data[1 + v]); // bridges[u] = [이웃 섬, 종류]들(다리는 양쪽으로 건넌다)type Bridge = [to: number, kind: number];const bridges: Bridge[][] = Array.from({ length: n + 1 }, (): Bridge[] => []);for (let i = 0; i < m; i++) {  const a = data[2 + n + 3 * i];  const b = data[3 + n + 3 * i];  const k = data[4 + n + 3 * i];  bridges[a].push([b, k]);  bridges[b].push([a, k]);} // 상태 = (섬, 분의 홀짝). time[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때const time: number[] = new Array<number>(2 * n + 2).fill(-1);time[2 * 1 + 0] = 0;const queue: number[] = [2];// shift()는 뒤의 것을 모두 당겨서 느리다. 머리 번호 head를 옮긴다for (let head = 0; head < queue.length; head++) {  const u = queue[head] >> 1;  const p = queue[head] & 1;  const t = time[queue[head]];  const visit = (v: number): void => {    const s = 2 * v + (1 - p);    if (time[s] === -1) {      time[s] = t + 1;      queue.push(s);    }  };  if (shelter[u] === 1) visit(u); // 쉼터에서 1분 기다린다  for (const [v, k] of bridges[u]) {    // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다    if (k === 0 || (k === 1) === (p === 1)) visit(v);  }} const first: number[] = [];let reached = 0;for (let v = 1; v <= n; v++) {  const even = time[2 * v];  const odd = time[2 * v + 1];  // 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽  const best = even === -1 ? odd : odd === -1 ? even : Math.min(even, odd);  if (best !== -1) reached++;  first.push(best);}console.log(reached);console.log(first.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;        boolean[] shelter = new boolean[n + 1];        for (int v = 1; v <= n; v++) {            st.nextToken();            shelter[v] = st.nval == 1;        }         // bridges.get(u) = {이웃 섬, 종류}들(다리는 양쪽으로 건넌다)        List<List<int[]>> bridges = new ArrayList<>();        for (int v = 0; v <= n; v++) bridges.add(new ArrayList<>());        for (int i = 0; i < m; i++) {            st.nextToken();            int a = (int) st.nval;            st.nextToken();            int b = (int) st.nval;            st.nextToken();            int k = (int) st.nval;            bridges.get(a).add(new int[] {b, k});            bridges.get(b).add(new int[] {a, k});        }         // 상태 = (섬, 분의 홀짝). time[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때        int[] time = new int[2 * n + 2];        Arrays.fill(time, -1);        time[2] = 0;        ArrayDeque<Integer> queue = new ArrayDeque<>();        queue.add(2);        while (!queue.isEmpty()) {            int state = queue.poll();            int u = state / 2, p = state % 2;            int t = time[state] + 1;            if (shelter[u] && time[2 * u + 1 - p] == -1) { // 쉼터에서 1분 기다린다                time[2 * u + 1 - p] = t;                queue.add(2 * u + 1 - p);            }            for (int[] bridge : bridges.get(u)) {                int v = bridge[0], k = bridge[1];                // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다                boolean open = k == 0 || (k == 1) == (p == 1);                if (open && time[2 * v + 1 - p] == -1) {                    time[2 * v + 1 - p] = t;                    queue.add(2 * v + 1 - p);                }            }        }         StringBuilder sb = new StringBuilder();        int reached = 0;        for (int v = 1; v <= n; v++) {            int even = time[2 * v], odd = time[2 * v + 1];            // 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽            int best = even == -1 ? odd : odd == -1 ? even : Math.min(even, odd);            if (best != -1) reached++;            sb.append(best).append(v < n ? ' ' : '\n');        }        System.out.print(reached + "\n" + 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 shelter = new bool[n + 1];        for (int v = 1; v <= n; v++) shelter[v] = data[1 + v] == "1";         // bridges[u] = (이웃 섬, 종류)들(다리는 양쪽으로 건넌다)        var bridges = new List<(int To, int Kind)>[n + 1];        for (int v = 0; v <= n; v++) bridges[v] = new List<(int To, int Kind)>();        for (int i = 0; i < m; i++)        {            int a = int.Parse(data[2 + n + 3 * i]), b = int.Parse(data[3 + n + 3 * i]), k = int.Parse(data[4 + n + 3 * i]);            bridges[a].Add((b, k));            bridges[b].Add((a, k));        }         // 상태 = (섬, 분의 홀짝). time[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때        var time = new int[2 * n + 2];        Array.Fill(time, -1);        time[2] = 0;        var queue = new Queue<int>();        queue.Enqueue(2);        while (queue.Count > 0)        {            int state = queue.Dequeue();            int u = state / 2, p = state % 2;            int t = time[state] + 1;            if (shelter[u] && time[2 * u + 1 - p] == -1) // 쉼터에서 1분 기다린다            {                time[2 * u + 1 - p] = t;                queue.Enqueue(2 * u + 1 - p);            }            foreach (var (v, k) in bridges[u])            {                // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다                bool open = k == 0 || (k == 1) == (p == 1);                if (open && time[2 * v + 1 - p] == -1)                {                    time[2 * v + 1 - p] = t;                    queue.Enqueue(2 * v + 1 - p);                }            }        }         var sb = new StringBuilder();        int reached = 0;        for (int v = 1; v <= n; v++)        {            int even = time[2 * v], odd = time[2 * v + 1];            // 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽            int best = even == -1 ? odd : odd == -1 ? even : Math.Min(even, odd);            if (best != -1) reached++;            sb.Append(best).Append(v < n ? ' ' : '\n');        }        Console.Write(reached + "\n" + sb);    }}

#include <algorithm>#include <iostream>#include <queue>#include <utility>#include <vector>using namespace std; int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    int n, m;    cin >> n >> m;    vector<int> shelter(n + 1);    for (int v = 1; v <= n; v++) cin >> shelter[v];     // bridges[u] = {이웃 섬, 종류}들(다리는 양쪽으로 건넌다)    vector<vector<pair<int, int>>> bridges(n + 1);    for (int i = 0; i < m; i++) {        int a, b, k;        cin >> a >> b >> k;        bridges[a].push_back({b, k});        bridges[b].push_back({a, k});    }     // 상태 = (섬, 분의 홀짝). when[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때    vector<int> when(2 * n + 2, -1);    queue<int> q;    when[2] = 0;    q.push(2);    while (!q.empty()) {        int state = q.front();        q.pop();        int u = state / 2, p = state % 2;        int t = when[state] + 1;        if (shelter[u] && when[2 * u + 1 - p] == -1) { // 쉼터에서 1분 기다린다            when[2 * u + 1 - p] = t;            q.push(2 * u + 1 - p);        }        for (auto [v, k] : bridges[u]) {            // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다            bool open = k == 0 || (k == 1) == (p == 1);            if (open && when[2 * v + 1 - p] == -1) {                when[2 * v + 1 - p] = t;                q.push(2 * v + 1 - p);            }        }    }     vector<int> first(n + 1);    int reached = 0;    for (int v = 1; v <= n; v++) {        int even = when[2 * v], odd = when[2 * v + 1];        // 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽        first[v] = even == -1 ? odd : odd == -1 ? even : min(even, odd);        if (first[v] != -1) reached++;    }    cout << reached << "\n";    for (int v = 1; v <= n; v++) cout << first[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 *shelter = malloc((n + 1) * sizeof(int));    for (int v = 1; v <= n; v++) scanf("%d", &shelter[v]);     // 인접 목록을 배열로: head[u]에서 시작해 next[e]로 따라가며 to[e], kind[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));    int *kind = 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, k;        scanf("%d %d %d", &a, &b, &k);        to[2 * i] = b; kind[2 * i] = k; next[2 * i] = head[a]; head[a] = 2 * i;        to[2 * i + 1] = a; kind[2 * i + 1] = k; next[2 * i + 1] = head[b]; head[b] = 2 * i + 1;    }     // 상태 = (섬, 분의 홀짝). time[2 * v + p] = v번 섬에 홀짝이 p인 분에 처음 있게 되는 때    int states = 2 * n + 2;    int *time = malloc(states * sizeof(int));    int *queue = malloc(states * sizeof(int)); // 상태마다 한 번만 들어간다    for (int s = 0; s < states; s++) time[s] = -1;    int qh = 0, qt = 0;    time[2] = 0;    queue[qt++] = 2;    while (qh < qt) {        int state = queue[qh++];        int u = state / 2, p = state % 2;        int t = time[state] + 1;        if (shelter[u] && time[2 * u + 1 - p] == -1) { // 쉼터에서 1분 기다린다            time[2 * u + 1 - p] = t;            queue[qt++] = 2 * u + 1 - p;        }        for (int e = head[u]; e != -1; e = next[e]) {            int v = to[e], k = kind[e];            // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다            int open = k == 0 || (k == 1) == (p == 1);            if (open && time[2 * v + 1 - p] == -1) {                time[2 * v + 1 - p] = t;                queue[qt++] = 2 * v + 1 - p;            }        }    }     int reached = 0;    for (int v = 1; v <= n; v++) {        if (time[2 * v] != -1 || time[2 * v + 1] != -1) reached++;    }    printf("%d\n", reached);    for (int v = 1; v <= n; v++) {        int even = time[2 * v], odd = time[2 * v + 1];        // 두 홀짝 가운데 닿은 쪽, 둘 다 닿았으면 이른 쪽        int best = even == -1 ? odd : odd == -1 ? even : (even < odd ? even : odd);        printf(v > 1 ? " %d" : "%d", best);    }    printf("\n");    free(shelter); free(head); free(next); free(to); free(kind); free(time); free(queue);    return 0;}

첫줄 = コンソール.数読み();n = 첫줄[0];m = 첫줄[1];// 목록은 10,000칸까지라 섬 번호에서 1을 빼 0번부터 둔다shelter = コンソール.数読み(); // bridges[u] = [이웃 섬, 종류]들(다리는 양쪽으로 건넌다)bridges = [];繰り返す (v = 0; v < n; v++){    bridges.追加([]);}繰り返す (i = 0; i < m; i++){    줄 = コンソール.数読み();    bridges[줄[0] - 1].追加([줄[1] - 1, 줄[2]]);    bridges[줄[1] - 1].追加([줄[0] - 1, 줄[2]]);} // 상태 = (섬, 분의 홀짝). 상태가 2n개라 목록 하나(10,000칸)에 못 담으니 홀짝마다 목록을 따로 둔다// seen[p][v] = v번 섬에 홀짝이 p인 분에 있어 본 적이 있는가seen = [新リスト(n, 偽), 新リスト(n, 偽)];first = 新リスト(n, -1);seen[0][0] = 真;first[0] = 0;reached = 1;// t분에 새로 나온 상태는 홀짝이 모두 같으니, 큐 대신 '이번 분의 섬들'을 한 층씩 넘긴다frontier = [0];t = 0;間 (frontier.個数 > 0){    p = t % 2;    q = 1 - p;    next = [];    それぞれ (u の中 frontier)    {        もし (shelter[u] == 1 && !seen[q][u])        {            seen[q][u] = 真;            next.追加(u);        }        それぞれ (b の中 bridges[u])        {            v = b[0];            k = b[1];            // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다            open = k == 0 || k == 1 && p == 1 || k == 2 && p == 0;            もし (open && !seen[q][v])            {                seen[q][v] = 真;                もし (first[v] == -1)                {                    first[v] = t + 1;                    reached++;                }                next.追加(v);            }        }    }    frontier = next;    t++;} コンソール.書く(reached);コンソール.書く(first);