e-olymp 4853. Кратчайший путь

Условие:

Задан неориентированный граф. Найдите кратчайший путь от вершины $start$ до вершины $end$.

Входные данные:

В первой строке находится два целых числа $n$ и $m$ $ (1 ≤ n ≤ 50000, 1 ≤ m ≤ 100000)$ — количества вершин и рёбер соответственно. Во второй строке заданы целые числа $start$ и $end$ — стартовая и конечная вершина соответственно. Далее идут $m$ строк, описывающие рёбра.

Выходные данные:

Если пути между $start$ и $end$ нет, то выведите $-1$. Иначе выведите в первой строке длину $l$ кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите $l + 1$ число — вершины этого пути.

Тесты:

№	Входные данные	Выходные данные
1	4 5 1 4 1 3 3 2 2 4 2 1 2 3	2 1 2 4
2	5 3 1 4 2 3 3 5 3 4	-1
3	5 4 1 4 1 2 2 3 3 5 3 4	3 1 2 3 4

Решение:

Поскольку нам необходимо найти кратчайшее расстояние между вершинами реализуем поиском в ширину. Запомним посещенные вершины в массиве [latex]used[/latex], родительские вершины в массиве [latex]parent[/latex], а план посещений в списке [latex]plan[/latex].

Изначально в списке [latex]plan[/latex] находится единственная вершина $start$. Каждый шаг начинается с того, что мы берем первую вершину из списка [latex]plan[/latex], отмечаем ее как посещенную, удаляем из списка и после посещаем все ее соседние вершины, которые еще не были посещены.

Когда очередь опустеет, обход в ширину обойдёт все достижимые из [latex]point[/latex] вершины, причём до каждой дойдёт кратчайшим путём. После того, как кратчайший путь найден — мы с помощью массива «предков» восстанавливаем его.

import cpp.vm.Gc;
import cpp.Lib;
import sys.io.*;

class Main {
	
    static function main() {
		var n = 5;
		var m = 4;
		
		var g = new Array < Array<Int> >(); 	//граф
		
		var taskIn = new Array < Array<Int> >();	//ввод
		
		for (i in 0...n){
			g[i] = new Array <Int>();
		}
		
		var start = 1; //начальная вершина
		var end = 4; //конечная вершина
		
		--start;
		--end;
		
		taskIn.push([2, 3]); //вводимые ребра
		taskIn.push([1, 2]);
		taskIn.push([3, 5]);
		taskIn.push([3, 4]);
		taskIn.push([4, 3]);
		
		
		
		for (x in taskIn){
			var v1 = --x[0]; // декремент -> нумерация с 0
			var v2 = --x[1];

			g[v1].push(v2);
			g[v2].push(v1);
			
		}
		
		var plan = new List<Int>();
		var used = new Array<Bool>();
		var parent = new Array<Int>();
		
		
		for (i in 0...n){
			used.push(false);
			parent.push(0);
		}
		
		
		plan.add(start);
		used [start] = true;
		parent [start] = start;
		
		var point : Int = start;

		//пока не достигли конца и пока план не пуст
		while (point != end && !plan.isEmpty()){  
			point = plan.first();
			plan.pop();
			
			for (x in g[point]){
				
				if (!used[x]){
					used[x] = true;
					plan.add(x);
					parent[x] = point;
				}
			}
		}
		

		var answ: String = "";	//ответ
		
		if (point == end){	//если достигли конца -> путь существует
			var path = new Array<Int>();
			
			while (point != start){
				path.push(point);
				point = parent[point];
			}
			
			path.push(start);
			path.reverse();
			
			trace (path.length - 1);
			for (x in path)
				answ += x + 1 + " ";
		}else{
			answ = -1 + "";
		}
		trace(answ);

		
    }
}

import cpp.vm.Gc;

import cpp.Lib;

import sys.io.*;

class Main {

static function main() {

var n = 5;

var m = 4;

var g = new Array < Array<Int> >(); //граф

var taskIn = new Array < Array<Int> >(); //ввод

for (i in 0...n){

g[i] = new Array <Int>();

}

var start = 1; //начальная вершина

var end = 4; //конечная вершина

--start;

--end;

taskIn.push([2, 3]); //вводимые ребра

taskIn.push([1, 2]);

taskIn.push([3, 5]);

taskIn.push([3, 4]);

taskIn.push([4, 3]);

for (x in taskIn){

var v1 = --x[0]; // декремент -> нумерация с 0

var v2 = --x[1];

g[v1].push(v2);

g[v2].push(v1);

}

var plan = new List<Int>();

var used = new Array<Bool>();

var parent = new Array<Int>();

for (i in 0...n){

used.push(false);

parent.push(0);

}

plan.add(start);

used [start] = true;

parent [start] = start;

var point : Int = start;

//пока не достигли конца и пока план не пуст

while (point != end && !plan.isEmpty()){

point = plan.first();

plan.pop();

for (x in g[point]){

if (!used[x]){

used[x] = true;

plan.add(x);

parent[x] = point;

}

var answ: String = ""; //ответ

if (point == end){ //если достигли конца -> путь существует

var path = new Array<Int>();

while (point != start){

path.push(point);

point = parent[point];

}

path.push(start);

path.reverse();

trace (path.length - 1);

for (x in path)

answ += x + 1 + " ";

}else{

answ = -1 + "";

}

trace(answ);

}

try online

Об авторе
Недавние публикации

Маша Лукьянова

Маша Лукьянова недавно публиковал (посмотреть все)

e-olymp 4853. Кратчайший путь - 14.06.2017
Алгоритм шифрования MARS - 06.05.2017
e-olymp 4000. Обход в глубину - 24.04.2017

Алексей Маслеев	Сергей Завада	Анастасия Улановская
Владислав Козачков	Николай Яковлев	Даша Тарабаева
Денис Швецов	Лена Наумова	Артур Тарасов
Евгений Кравчук	Иоанна Васильева	Дарья Пиндус
Артём Мисесин	Даша Кивганова	Кирилл Автомонов
Алёна Ищук	Александр Зайченко	Маша Лукьянова
Игорь Варламов	Геннадий Муржи

haxe

Учебные материалы по программированию

e-olymp 4853. Кратчайший путь

Условие:

Входные данные:

Выходные данные:

Тесты:

Решение:

Понравилось это:

Похожее

Добавить комментарий Отменить ответ

Условие:

Входные данные:

Выходные данные:

Тесты:

Решение:

Поделиться ссылкой:

Понравилось это:

Похожее

Добавить комментарий Отменить ответ