Условие

В неориентированном графе требуется найти минимальный путь между двумя вершинами.

Примеры

Ввод:

10 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 5 4 Вывод:

2 5 2 4

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.LinkedList
import java.util.Queue

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))
    
    // Чтение количества вершин
    val n = reader.readLine().trim().toInt()
    
    // Чтение матрицы смежности
    val adjMatrix = Array(n) {
        reader.readLine().trim().split(" ").map { it.toInt() }.toIntArray()
    }
    
    // Чтение начальной и конечной вершин (приводим к 0-индексации)
    val (start, end) = reader.readLine().trim().split(" ").map { it.toInt() - 1 }
    
    // Если начальная и конечная вершины совпадают, выводим 0 и завершаем программу.
    if (start == end) {
        writer.write("0\\n")
        writer.flush()
        return
    }
    
    // Массив для отслеживания посещённых вершин
    val visited = BooleanArray(n)
    // Массив для восстановления пути: для каждой вершины хранится предыдущая вершина в пути
    val prev = IntArray(n) { -1 }
    
    // Очередь для BFS
    val queue: Queue<Int> = LinkedList()
    visited[start] = true
    queue.add(start)
    
    // Флаг, указывающий на то, что путь найден
    var found = false
    
    // Выполнение BFS
    while (queue.isNotEmpty()) {
        val current = queue.poll()
        // Если достигли конечной вершины, выходим из цикла
        if (current == end) {
            found = true
            break
        }
        // Перебираем всех соседей текущей вершины
        for (neighbor in 0 until n) {
            if (adjMatrix[current][neighbor] == 1 && !visited[neighbor]) {
                visited[neighbor] = true
                prev[neighbor] = current
                queue.add(neighbor)
            }
        }
    }
    
    // Если путь не найден, выводим -1
    if (!found) {
        writer.write("-1\\n")
    } else {
        // Восстанавливаем путь, двигаясь от конечной вершины к начальной с помощью массива prev
        val path = mutableListOf<Int>()
        var current = end
        while (current != -1) {
            // Добавляем вершину в путь (возвращаем к 1-индексации)
            path.add(current + 1)
            current = prev[current]
        }
        path.reverse()
        
        // Вывод длины пути (количество рёбер = количество вершин минус 1)
        writer.write("${path.size - 1}\\n")
        // Вывод последовательности вершин пути через пробел
        writer.write(path.joinToString(" ") + "\\n")
    }
    
    writer.flush()
    writer.close()
}