Module: Dijkstra 算法


Problem

8/14

O(M logN) c 集合中的 Dijkstra 算法：开始 (C++)

Theory Click to read/hide

由于 Dijkstra 算法的原始实现的渐近行为是： \(O(n^2 + m)\)，那么随着顶点数量的增加，工作速度变得不尽如人意。
 可以使用各种数据结构进行改进： Fibonacci 堆、集合 集合或优先队列 priority_queue。 
考虑一个带有 set 的例子，结果，最终的渐近线是： \(O(n log (m))\) , 详情。

Problem

给你一个有向加权图。找出从一个给定顶点到另一个顶点的最短距离。
 
输入
第一行包含三个数字：N、M、S和F（1≤N≤100、1≤S、F≤N），其中N–图的顶点数，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!