Module: Algoritmo de Dijkstra


Problem

9/14

Algoritmo de Dijkstra en O(M logN) con prioridad_cola: Inicio (C++)

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 <queue>
#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);
		 for (int i = 0; i < m; i++)
		{
			int x, y, z;
			cin >> x >> y >> z;
			g[x].push_back(make_pair(y, z));
		}

		vector<int> d(n+1, INF);
		d[s] = 0;
		priority_queue < pair<int, int> > q;
		q.push(make_pair(0, s));
		while (!q.empty()) {
			int v = q.top().second, cur_d = -q.top().first;
			q.pop();
			if (cur_d > d[v])  continue;

			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]) {
					d[to] = d[v] + len;
					
					q.push(make_pair(-d[to], to));
				}
			}
		}    
}

     

Program check result

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