Module: Algoritmo de Dijkstra


Problem

8/14

Algoritmo de Dijkstra en O(M logN) conjunto c: Inicio (C++)

Theory Click to read/hide

Dado que el comportamiento asintótico de la implementación ingenua del algoritmo de Dijkstra es: \(O(n^2 + m)\), entonces a medida que aumenta el número de vértices, la velocidad de trabajo se vuelve insatisfactoria.
 Se pueden usar varias estructuras de datos para mejorar: Montones de Fibonacci, conjunto conjuntos o una cola de prioridad priority_queue. 
Considere un ejemplo con set, como resultado, la asintótica final es: \(O(n log (m))\) , detalles.

Problem

Se le proporciona un gráfico ponderado dirigido. Encuentra la distancia más corta de un vértice dado a otro.
 
Entrada
La primera línea contiene tres números: N, M, S y F (1≤ N≤ 100, 1≤ S, F≤ N), donde N – número de vértices del gráfico, M – número de costillas,  S– vértice inicial y F – final. En las próximas N líneas, ingrese N números cada uno, sin exceder 100, – matriz de adyacencia gráfica, donde -1 significa que no hay borde entre los vértices, y cualquier número no negativo – la presencia de una arista de peso dado. Los ceros se escriben en la diagonal principal de la matriz.
 
Salida
Se requiere mostrar la distancia deseada o -1 si no hay camino entre los vértices especificados.

Ejemplos

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
# Entrada Salida
1 4 4 3 4
3 1 3
1 2 3
2 4 3
3 4 10 		9
Write the program below 
#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];
	}

     

Program check result

To check the solution of the problem, you need to register or log in!