There are n islands numbered 1 to n.
There are m bridges between them, and a bridge "a b k" joins island a and island b and has kind k.
A bridge can be crossed in both directions, and crossing takes exactly 1 minute.
There may be several bridges between the same two islands.
A traveller is on island 1 at minute 0.
Starting to cross a bridge at minute t brings you to the other island at minute t + 1.
A bridge of kind 0 can be started at any minute.
A bridge of kind 1 can be started only when t is odd, and a bridge of kind 2 only when t is even (0 is even).
Once started, a crossing is always finished.
For each island you are told whether it has a shelter. If sᵢ is 1, island i has a shelter.
On an island with a shelter you may wait 1 minute, any number of times.
On an island without a shelter you cannot wait: you must start crossing a bridge in the very minute you arrive. If no bridge can be started in that minute, you cannot go on from there.
The same holds on island 1 at minute 0. If island 1 has no shelter, you must start crossing a bridge at minute 0.
You may pass the same island and the same bridge any number of times.
For each island, find the earliest minute at which the traveller can be on it.
The value for island 1 is 0, and the value for an island that can never be reached is -1.
On the first line print the number of islands that can be reached. Island 1 counts.
On the second line print the values for islands 1 to n in order, separated by single spaces.
Input
The first line has n and m, the second line s₁ … sₙ, and each of the next m lines has a, b and k. Numbers on a line are separated by one space. 1 ≤ n ≤ 9,000, 0 ≤ m ≤ 9,000, sᵢ is 0 or 1, 1 ≤ a, b ≤ n, a ≠ b, k is 0, 1 or 2. All are integers
Output
First line: the number of reachable islands. Second line: the earliest minute for each of the n islands, or -1 if unreachable
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
This is breadth-first search (BFS), but what you mark as visited is not 'an island' but '(island, parity of the minute)'. In example 1 you first reach island 2 at minute 1, an odd minute, so the kind-2 bridge cannot be started. You have to go round 1 → 5 → 6 → 1 → 2 and be on island 2 again at minute 4 (even) to go on to island 3. Trap one: an ordinary BFS that visits each island once never puts island 2 back in the queue, so it prints -1 for islands 3 and 4. There are 2n states, and the answer is the earlier of the two parities. Trap two: a bridge is judged by the parity of the minute you leave, not the minute you arrive. A crossing that leaves at minute 0 and arrives at minute 1 is on the 'even' side. Trap three: waiting works only at a shelter. Allow waiting everywhere and island 3 in example 1 becomes 3; forget shelters and island 3 in example 2 becomes -1. Waiting can be added as a 1-minute move to 'the same island, the other parity'. For the queue use Python collections.deque (list.pop(0) shifts every later item and is slow), Java ArrayDeque, C# Queue<T>, C++ std::queue, and in JS, TS and C an array with a 'head index' (JS shift() also shifts the rest). Packing a state into one number such as 2 * v + p lets one array hold everything. Craykon lists hold at most 10,000 items, so a 2n-item NewList(2 * n, -1) stops once n is over 5,000. So keep one list per parity (two NewList(n, false)), and, since all states found in the same minute have the same parity, pass along 'the list of islands for this minute' layer by layer instead of a queue.
Pythonmain.py · 44 lines
import sysfrom collections import dequedef 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()
JavaScriptmain.js · 51 lines
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(" "));
TypeScriptmain.ts · 54 lines
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(" "));
JavaMain.java · 67 lines
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); }}
C#Main.cs · 64 lines
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); }}
C++main.cpp · 60 lines
#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;}
Cmain.c · 65 lines
#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;}
Craykonmain.cray · 65 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];// 목록은 10,000칸까지라 섬 번호에서 1을 빼 0번부터 둔다shelter = Console.ReadNumbers();// bridges[u] = [이웃 섬, 종류]들(다리는 양쪽으로 건넌다)bridges = [];for (v = 0; v < n; v++){ bridges.Add([]);}for (i = 0; i < m; i++){ 줄 = Console.ReadNumbers(); bridges[줄[0] - 1].Add([줄[1] - 1, 줄[2]]); bridges[줄[1] - 1].Add([줄[0] - 1, 줄[2]]);}// 상태 = (섬, 분의 홀짝). 상태가 2n개라 목록 하나(10,000칸)에 못 담으니 홀짝마다 목록을 따로 둔다// seen[p][v] = v번 섬에 홀짝이 p인 분에 있어 본 적이 있는가seen = [NewList(n, false), NewList(n, false)];first = NewList(n, -1);seen[0][0] = true;first[0] = 0;reached = 1;// t분에 새로 나온 상태는 홀짝이 모두 같으니, 큐 대신 '이번 분의 섬들'을 한 층씩 넘긴다frontier = [0];t = 0;while (frontier.Count > 0){ p = t % 2; q = 1 - p; next = []; foreach (u in frontier) { if (shelter[u] == 1 && !seen[q][u]) { seen[q][u] = true; next.Add(u); } foreach (b in bridges[u]) { v = b[0]; k = b[1]; // 떠나는 분이 홀수면 1번, 짝수면 2번 다리가 열려 있다 open = k == 0 || k == 1 && p == 1 || k == 2 && p == 0; if (open && !seen[q][v]) { seen[q][v] = true; if (first[v] == -1) { first[v] = t + 1; reached++; } next.Add(v); } } } frontier = next; t++;}Console.WriteLine(reached);Console.WriteLine(first);