Олимпиадный тренинг

Задача . BFS: Начало (C++)


Задача

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

Примеры
№ Входные данные Выходные данные
1 5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5		 3

time 1000 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6466
Комментарий учителя

Ваш ответ

C++
Напишите программу ниже 
#include <iostream>
#include <vector>
#include <queue>

using namespace std;


int main()
{
        int n;
        cin >> n;  // число вершин 
        vector <vector <int> > g (n, vector<int>(n, 0));    //матрица смежности
        for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                        cin >> g[i][j];
        
        int start;
        int finish;
        cin  >> start;
        cin  >> finish;
        if(start == finish)   // если точка старта совпадает с концом
        {
           cout<<"0";
           return 0;
        }
        vector <int>  d(n, -1);  // массив длин (хранит длину до данной вершины)
        d[start-1] = 0;
        queue <int> q;   // создание очереди  из вершин
        q.push(start-1);  // добавление в очередь точки старта 

       vector <bool> used(n,false);    // булевский массив посещений (true если данная вершина была обработана и false если вершина не обработана) 
       used[start-1] = true;   // помечаем стартовую вершину, что ее уже посетили
        while (!q.empty())
        {                        
        }
        cout << d[finish-1];
        return 0;
}
     

Загруженные файлы
Нет