Module: Dijkstra'nın algoritması


Problem

9/14

Dijkstra'nın O(M logN) algoritması ve Priority_queue ile: Başlat (C++)

Problem

Size yönlendirilmiş ağırlıklı bir grafik verilir. Belirli bir köşeden diğerine en kısa mesafeyi bulun.
 
Giriş
İlk satır üç sayı içerir: N, M, S ve F (1≤ N≤ 100, 1≤ S, F≤ N), burada N – grafik köşe sayısı, M – kaburga sayısı,  S– ilk tepe noktası ve F –ndash; son. Sonraki N satırın her birine 100'ü geçmeyecek şekilde N sayı girin, – grafik bitişiklik matrisi, burada -1, köşeler arasında kenar olmaması ve negatif olmayan herhangi bir sayı anlamına gelir -ndash; verilen ağırlıkta bir kenarın varlığı. Matrisin ana köşegenine sıfırlar yazılır.
 
Çıktı
İstenilen mesafenin veya belirtilen köşeler arasında yol yoksa -1 gösterilmesi gerekir.

Örnekler

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++
# Girdi Çıktı
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!