Module: Dijkstra의 알고리즘


Problem

8/14

O(M logN) c 집합의 Dijkstra 알고리즘: 시작(C++)

Theory Click to read/hide

Dijkstra 알고리즘의 순진한 구현의 점근적 동작은 \(O(n^2 + m)\)이므로 정점 수가 증가함에 따라 작업 속도가 만족스럽지 않게 됩니다.
 개선을 위해 다양한 데이터 구조를 사용할 수 있습니다: 피보나치 힙, 세트 세트 또는 우선 순위 대기열 priority_queue. 
set의 예를 고려하면 최종 점근선은 다음과 같습니다. \(O(n log (m))\) , 세부정보.

Problem

방향 가중치 그래프가 제공됩니다. 주어진 정점에서 다른 정점까지의 최단 거리를 찾습니다.
 
입력
첫 번째 줄에는 N, M, S 및 F(1≤ N≤ 100, 1≤ S, F≤ N)의 세 숫자가 포함되어 있습니다. 그래프 꼭지점의 수, M – 갈비뼈의 수,  S– 초기 정점 및 F – 결정적인. 다음 N 줄에 각각 100을 넘지 않는 N개의 숫자를 입력하세요. – 그래프 인접 행렬, 여기서 -1은 꼭짓점 사이에 가장자리가 없고 음수가 아닌 숫자를 의미합니다. 주어진 가중치의 가장자리가 존재합니다. 0은 매트릭스의 주대각선에 기록됩니다.
 
출력
지정된 꼭짓점 사이에 경로가 없으면 원하는 거리 또는 -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!