Module: Dijkstra-Algorithmus


Problem

9/14

Dijkstra-Algorithmus für O(M logN) mit priority_queue: Anfang (C++)

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