Module: दिज्क्स्ट्रा का एल्गोरिथ्म


Problem

8/14

ओ (एम लॉग एन) सी सेट में डिजस्ट्रा का एल्गोरिदम: स्टार्ट (सी ++)

Theory Click to read/hide

चूंकि दिज्क्स्ट्रा के एल्गोरिथ्म के सहज कार्यान्वयन का स्पर्शोन्मुख व्यवहार है:  कार्य की गति असंतोषजनक हो जाती है।
 विभिन्न डेटा संरचनाओं का उपयोग सुधार के लिए किया जा सकता है: फाइबोनैचि ढेर, सेट सेट, या प्राथमिकता कतार प्राथमिकता_कतार. 
सेट के साथ एक उदाहरण पर विचार करें, परिणामस्वरूप, अंतिम स्पर्शोन्मुख है: \(O(n log (m))\) , विवरण।

Problem

आपको एक निर्देशित भारित ग्राफ दिया जाता है। एक दिए गए शीर्ष से दूसरे शीर्ष तक की न्यूनतम दूरी ज्ञात कीजिए।
 
इनपुट
पहली पंक्ति में तीन संख्याएँ होती हैं: N, M, S और F (1≤ N≤ 100, 1≤ S, F≤ N), जहाँ N – ग्राफ़ शीर्षों की संख्या, M – पसलियों की संख्या,  सं– आरंभिक शीर्ष, और F – अंतिम। अगली एन पंक्तियों में, प्रत्येक संख्या एन संख्या दर्ज करें, 100 से अधिक नहीं, – ग्राफ़ आसन्न मैट्रिक्स, जहाँ -1 का अर्थ है शीर्षों के बीच कोई किनारा नहीं, और कोई भी गैर-ऋणात्मक संख्या – दिए गए वजन के किनारे की उपस्थिति। मैट्रिक्स के मुख्य विकर्ण पर शून्य लिखे जाते हैं।
 
आउटपुट
वांछित दूरी प्रदर्शित करना आवश्यक है या -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!