[알고리즘] 1753 / 최단경로 / C++

 

 

#다익스트라

 

다익스트라를 구현하는 그 자체의 문제였다.

ios_base 이 코드를 추가해도 계속 시간초과가 떴는데  아무래도 다익스트라 알고리즘과 priority queue 이해도 부족이 아니었나 싶다.

 

🔽 시간초과 코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define MAX 20001

// 한점시작, 모든거리: 다익스트라
// 간선, 인접리스트 저장
// 거리배열 무한대 초기화

int N, M;
int INF = 1000000000;
int dist[MAX];
int visited[MAX];
vector<pair<int, int>> vec[MAX];
priority_queue<pair<int, int>> pq;
int st, ed;

void dijkstra(int start) {
	dist[start] = 0;
	
	pq.push(make_pair(start, 0));

	while (!pq.empty()) {
		int current = pq.top().first;
		int distance = -1 * pq.top().second; // 짧은 것이 먼저 오도록 음수화
		pq.pop();

		// 이전에 구한 거리가 더 최소인 경우 스킵
		if (dist[current] < distance) continue;
		for (int i = 0; i < vec[current].size(); i++) {
			int next = vec[current][i].first;
			int nextdist = distance + vec[current][i].second;

			if (nextdist < dist[next]) {
				dist[next] = nextdist;
				pq.push(make_pair(next, -1 * nextdist));
			}
		}
	}

	
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	cin >> st;
	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}

	for (int i = 0; i < M; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		vec[from].push_back({ to,cost });
	}
	
	dijkstra(st);

	// cout << dist[ed] << endl;
	for (int i = 1; i <= N; i++) {
		if(dist[i]<1000000000) cout << dist[i] << "\n";
		else cout << "INF" << "\n";
	}

	return 0;
}

 

 

✅ 해결코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define MAX 20001

// 한점시작, 모든거리: 다익스트라
// 간선, 인접리스트 저장
// 거리배열 무한대 초기화

int N, M;
int INF = 1000000000;
int dist[MAX];
int visited[MAX];
vector<pair<int, int>> vec[MAX];
priority_queue<pair<int, int>> pq;
int st, ed;

void dijkstra(int start) {
	dist[start] = 0;
	
	pq.push(make_pair(0, start));

	while (!pq.empty()) {
		int current = pq.top().second;
		int distance = -1 * pq.top().first; // 짧은 것이 먼저 오도록 음수화
		pq.pop();

		// 이전에 구한 거리가 더 최소인 경우 스킵
		if (dist[current] < distance) continue;
		for (int i = 0; i < vec[current].size(); i++) {
			int next = vec[current][i].first;
			int nextdist = distance + vec[current][i].second;

			if (nextdist < dist[next]) {
				dist[next] = nextdist; // dist에 들어가는 수는 양수
				pq.push(make_pair(-1 * nextdist, next ));
			}
		}
	}

	
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	cin >> st;
	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}

	for (int i = 0; i < M; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		vec[from].push_back({ to,cost });
	}
	
	dijkstra(st);

	for (int i = 1; i <= N; i++) {
		if(dist[i]<1000000000) cout << dist[i] << "\n";
		else cout << "INF" << "\n";
	}

	return 0;
}

 

 

 

참고하기 제일 좋은 블로그(동빈나)

https://blog.naver.com/PostView.naver?blogId=ndb796&logNo=221234424646&redirect=Dlog&widgetTypeCall=true&directAccess=false 

23. 다익스트라(Dijkstra) 알고리즘