Модуль: Алгоритм Дейкстры


Задача

8/14

Алгоритм Дейкстры за O(M logN) c set: Начало (C++)

Теория Нажмите, чтобы прочитать/скрыть

Так как асимптотика наивной реализации алгоритма Дейкстра: \(O(n^2 + m)\), то с увеличением количества вершин скорость работы становиться неудовлетворительной.
 Для улучшения можно использовать различные структуры данных: Фибоначчиевы кучи, множества set или очередь с приоритетом priority_queue. 
Рассмотрим пример с set, в результате итоговая асимптотика получается: \(O(n log (m))\), подробнее.

Задача

Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой.
 
Входные данные
В первой строке содержатся три числа: N, M, S и F (1≤ N≤ 100, 1≤ S, F≤ N), где N – количество вершин графа, M – количество ребер,  S – начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.
 
Выходные данные
Требуется вывести искомое расстояние или -1, если пути между указанными вершинами не существует.

Примеры
№ Входные данные Выходные данные
1 4 4 3 4
3 1 3
1 2 3
2 4 3
3 4 10		 9


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

Комментарий учителя

Вставьте недостающие фрагменты кода
C++
Напишите программу ниже 
#include <iostream>
#include <set>
#include <vector>
using namespace std;

	const int INF = 1000000000;

	int main() {
		int n, m ,s, f;
		cin >> n>>m>>s>>f;
		
		vector < vector < pair<int, int> > > g(n+1);
		// чтение графа  
		vector<int> d(n+1, INF);
		d[s] = 0;
		set < pair<int, int> > q;
		q.insert(make_pair(d[s], s));
		while (!q.empty()) {
			int v = q.begin()->second;
			q.erase(q.begin());

			for (size_t j = 0; j < g[v].size(); ++j) {
				int to = g[v][j].first,
					len = g[v][j].second;
				if (d[v] + len < d[to]) {
					q.erase(make_pair(d[to], to));
					d[to] = d[v] + len;
					q.insert(make_pair(d[to], to));
				}
			}
		}

		if (d[f] == 10000000)
			cout << "-1";
		else
			cout << d[f];
	}

     

Результат проверки программы 

Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!