4852. Кратчайшее расстояние

Дан ориентированный граф. Найдите расстояние от вершины x до всех остальных вершин графа.

Вход. В первой строке содержатся два натуральных числа n и x (1 ≤ n ≤ 1000, 1 ≤ x ≤ n) – количество вершин в графе и стартовая вершина соответственно. Далее в n строках по n чисел – матрица смежности графа: в i-ой строке на j-ом месте стоит “1”, если вершины i и j соединены ребром, и “0”, если ребра между ними нет. На главной диагонали матрицы стоят нули.

Выход. Выведите через пробел числа d₁, d₂, ..., d_n, где d_i равно -1, если путей между x и i нет, в противном случае это минимальное расстояние между x и i.

Пример входа	Пример выхода
6 5 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0	2 2 1 1 0 -1

РЕШЕНИЕ

графы – поиск в ширину

Анализ алгоритма

В задаче необходимо реализовать поиск в ширину, построив массив кратчайших расстояний dist от истока до всех вершин. Поскольку количество вершин не более 1000, то граф можно хранить в виде матрицы смежности.

Пример

Приведенный в примере граф имеет вид:

Реализация алгоритма

Объявим массив g для хранения графа, а также дополнительные массивы used и dist для реализации поиска в ширину. dist[i] хранит кратчайшее расстояние от истока до вершины i.

#define MAX 1010

int g[MAX][MAX], used[MAX], dist[MAX];

Функция bfs совершает поиск в ширину из вершины start. Очередь реализуем в виде локального массива q размера MAX (в любой момент времени количество вершин в очереди будет не больше чем количество вершин в графе). Head и Tail – указатели на голову и конец очереди.

void bfs(int start)

{

memset(used,0,sizeof(used));

memset(dist,-1,sizeof(dist));

dist[start] = 0;

int q[MAX], Head = 0, Tail = 1;

q[Head] = start; used[start] = 1;

while(Head < Tail)

{

int v = q[Head++];

Если из v имеется ребро в i, и при этом вершина i еще не пройдена, то идем в нее (ребро (v, i) является ребром дерева при поиске в ширину).

for(int i = 1; i <= n; i++)

if (g[v][i] && !used[i])

{

q[Tail++] = i;

used[i] = 1;

dist[i] = dist[v] + 1;

}

}

}

Основная часть программы. Читаем входные данные.

scanf("%d %d",&n,&x);

for(i = 1; i <= n; i++)

for(j = 1; j <= n; j++)

scanf("%d",&g[i][j]);

Запускаем поиск в ширину из вершины x.

bfs(x);

Выводим искомые кратчайшие расстояния.

printf("%d",dist[1]);

for(i = 2; i <= n; i++)

printf(" %d",dist[i]);

printf("\n");

Реализация алгоритма – STL

Объявим массив g для хранения графа, а также дополнительные массивы used и dist для реализации поиска в ширину. dist[i] хранит кратчайшее расстояние от истока до вершины i.

#define MAX 1010

int g[MAX][MAX], dist[MAX];

Функция bfs совершает поиск в ширину из вершины start.

void bfs(int start)

{

memset(dist,-1,sizeof(dist));

dist[start] = 0;

queue<int> q;

q.push(start);

while(!q.empty())

{

int v = q.front(); q.pop();

Если из v имеется ребро в to, и при этом вершина to еще не пройдена, то идем в нее (ребро (v, to) является ребром дерева при поиске в ширину).

for(int to = 1; to <= n; to++)

if (g[v][to] && (dist[to] == -1))

{

q.push(to);

dist[to] = dist[v] + 1;

}

}

}

Основная часть программы. Читаем входные данные.

scanf("%d %d",&n,&x);

for(i = 1; i <= n; i++)

for(j = 1; j <= n; j++)

scanf("%d",&g[i][j]);

Запускаем поиск в ширину из вершины x.

bfs(x);

Выводим искомые кратчайшие расстояния.

for(i = 1; i <= n; i++)

printf("%d ",dist[i]);

printf("\n");

Java реализация

import java.util.*;

//import java.io.*;

public class Main

{

static int n, x;

static int g[][];

static int dist[];

static void dfs(int start)

{

dist[start] = 0;

Queue<Integer> q = new LinkedList<Integer>();

q.add(start);

while(!q.isEmpty())

{

int v = q.poll();

for(int to = 1; to <= n; to++)

if ((g[v][to] == 1) && (dist[to] == -1))

{

q.add(to);

dist[to] = dist[v] + 1;

}

}

}

public static void main(String[] args) // throws IOException

{

//Scanner con = new Scanner(new FileReader ("4852.in"));

Scanner con = new Scanner(System.in);

n = con.nextInt();

x = con.nextInt();

g = new int[n+1][n+1];

dist = new int[n+1];

Arrays.fill(dist, -1);

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

g[i][j] = con.nextInt();

dfs(x);

for(int i = 1; i <= n; i++)

System.out.print(dist[i] + " ");

System.out.println();

con.close();

}

}