Problem

8/14

Thuật toán Dijkstra trong bộ O(M logN) c: Start (C++)

Theory Click to read/hide

Vì hành vi tiệm cận của việc triển khai thuật toán Dijkstra ngây thơ là: \(O(n^2 + m)\), nên khi số lượng đỉnh tăng lên, tốc độ làm việc trở nên không đạt yêu cầu.
 Có thể sử dụng nhiều cấu trúc dữ liệu khác nhau để cải thiện: Đống Fibonacci, bộ bộ hoặc hàng đợi ưu tiên priority_queue. 
Xem xét một ví dụ với set, kết quả là tiệm cận cuối cùng là: \(O(n log (m))\) , chi tiết.

Problem

Bạn được cung cấp một biểu đồ trọng số có hướng. Tìm khoảng cách ngắn nhất từ ​​đỉnh này đến đỉnh khác.
 
Đầu vào
Dòng đầu tiên chứa ba số: N, M, S và F (1≤ N≤ 100, 1≤ S, F≤ N), trong đó N – số đỉnh của đồ thị, M – số lượng xương sườn,  S– đỉnh ban đầu và F – cuối cùng. Trong N dòng tiếp theo, hãy nhập N số mỗi dòng, không quá 100, – ma trận kề của đồ thị, trong đó -1 có nghĩa là không có cạnh giữa các đỉnh và bất kỳ số không âm nào – sự hiện diện của một cạnh của trọng lượng nhất định. Các số 0 được viết trên đường chéo chính của ma trận.
 
Đầu ra
Cần hiển thị khoảng cách mong muốn hoặc -1 nếu không có đường đi giữa các đỉnh đã chỉ định.

Ví dụ <đầu>

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++
# Đầu vào Đầu ra
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!