Module: ダイクストラのアルゴリズム


Problem

8/14

O(M logN) c set のダイクストラのアルゴリズム: 開始 (C++)

Theory Click to read/hide

ダイクストラのアルゴリズムの単純な実装の漸近動作は次のとおりであるため、\(O(n^2 + m)\) となり、頂点の数が増加すると、次のようになります。仕事のスピードが物足りなくなって
しまいます。 改善のためにさまざまなデータ構造を使用できます: フィボナッチ ヒープ、セット セット、または優先キューpriority_queue.
set を使用した例を考えてみましょう。その結果、最終的な漸近線は次のようになります。\(O(n log (m))\) 、詳細。

Problem

有向加重グラフが表示されます。指定された頂点から別の頂点までの最短距離を見つけます。
 
入力
最初の行には、N、M、S、および F (1≤ N≤ 100、1≤ S、F≤ N) の 3 つの数字が含まれています。グラフ頂点の数、M –肋骨の数、  S–初期頂点と F –最後の。次の N 行に、それぞれ N 個の数字を入力します (100 を超えない)。グラフ隣接行列。-1 は頂点間にエッジがないことを意味し、負ではない数値を意味します。指定された重みのエッジの存在。ゼロは行列の主対角に書き込まれます。
 
出力
希望の距離を表示するか、指定した頂点間にパスがない場合は -1 を表示する必要があります。

例 <頭> <本体>

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++
# 入力 出力
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 <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!