Problem

8/14

خوارزمية Dijkstra في مجموعة O (M logN) c: ابدأ (C ++)

Theory Click to read/hide

نظرًا لأن السلوك المقارب للتنفيذ الساذج لخوارزمية Dijkstra هو: & nbsp؛ \ (O (n ^ 2 + m) \) ، فكلما زاد عدد الرؤوس ، سرعة العمل تصبح غير مرضية.
& nbsp؛ يمكن استخدام هياكل البيانات المختلفة للتحسين: & nbsp؛ Fibonacci heaps، set مجموعات أو قائمة انتظار ذات أولوية & nbsp؛ priority_queue. & nbsp؛
ضع في اعتبارك مثالًا باستخدام set ، ونتيجة لذلك ، فإن المقاربات النهائية هي: & nbsp؛ \ (O (n log (m)) \) ، التفاصيل .

Problem

يتم إعطاؤك رسم بياني مرجح موجه. أوجد أقصر مسافة من رأس معين إلى آخر.
& nbsp؛
إدخال
يحتوي السطر الأول على ثلاثة أرقام: N و M و S و F (1 & le؛ N & le؛ 100، 1 & le؛ S، F & le؛ N) ، حيث N & ndash؛ عدد رؤوس الرسم البياني M & ndash؛ عدد الأضلاع ، نبسب ؛ ال & ndash؛ الرأس الأولي و F & ndash؛ أخير. في السطور N التالية ، أدخل أرقام N لكل منها ، بما لا يتجاوز 100 ، & ndash؛ مصفوفة تجاور الرسم البياني ، حيث يعني -1 عدم وجود حافة بين الرؤوس وأي رقم غير سالب & ndash؛ وجود حافة وزن معين. الأصفار مكتوبة على القطر الرئيسي للمصفوفة.
& nbsp؛
الإخراج
مطلوب عرض المسافة المرغوبة أو -1 إذا لم يكن هناك مسار بين الرؤوس المحددة.

أمثلة <الجسم>
# إدخال الإخراج
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!