Решение задачи №127 «Путь» с ACMP

Условие задачи

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

Входные данные
Во входном файле INPUT.TXT записано сначала число N - количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной.

Выходные данные
В выходной файл OUTPUT.TXT выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.

Решение на C++


    #include<iostream>

#include<queue>

using namespace std;

int main() {

	int n,i,j,k,f,s;queue<int> q;

	cin>>n;int a[n][n],d[n];

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

		{

		d[i]=1000000000;

		for(j=0;j<n;++j)cin>>a[i][j];}

	cin>>s>>f;s--;f--;

	d[s]=0; q.push(s);

	while(!q.empty()){i=q.front();q.pop();

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

			if(a[i][j]&&d[j]>d[i]+1){

				d[j]=d[i]+1;q.push(j);}}

	if(d[f]<1000000000)cout<<d[f];

	else cout<<-1;

return 0;}

Условия задач взяты с сайта acmp.ru