Module: Dijkstra-Algorithmus


Problem

8/14

Dijkstra-Algorithmus für O(M logN) c set: Start (C++)

Theory Click to read/hide

Seit der Asymptoik der naiven Umsetzung des Dextra-Algorithmus:\(O(n^2 + m)\, mit der Erhöhung der Zahl der Spitzen ist die Arbeitsgeschwindigkeit unbefriedigend geworden.
Zur Verbesserung können verschiedene Datenstrukturen verwendet werden: Auftrieb, Vielzahl Menge oder Prioritätprior_queue.
Mal sehen. Mengedie resultierende Asymptomie ist:- Ja.♪ Details♪

Problem

Es wurde ein orientiertes gewichtetes Diagramm angegeben. Finden Sie den kürzesten Abstand von einem bestimmten Scheitelpunkt zum anderen.
 
Eingabe
Die erste Zeile enthält drei Zahlen: N, M, S und F (1≤ N≤ 100, 1≤ S, F≤ N), wobei N – die Anzahl der Eckpunkte des Graphen, M – die Anzahl der Kanten,  S – der Anfangsscheitelpunkt und F – der Endpunkt ist. In den nächsten N Zeilen werden N Zahlen eingegeben, die nicht größer als 100 sind, – die Adjazenzmatrix des Graphen, wobei -1 bedeutet, dass keine Kante zwischen den Eckpunkten fehlt und jede nicht negative Zahl die Anwesenheit einer Kante dieses Gewichts ist. Auf der Hauptdiagonale der Matrix sind Nullen geschrieben.
 
Ausgabe
Sie möchten den gewünschten Abstand oder -1 anzeigen, wenn kein Pfad zwischen den angegebenen Scheitelpunkten vorhanden ist.

Beispiele
№ Eingabe Ausgabe
1 4 4 3 4
3 1 3
1 2 3
2 4 3
3 4 10		 9

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++
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!