백준 1753 최단경로

문제 : https://www.acmicpc.net/problem/1753

 

서론

다익스트라 방법으로 풀이했으나 시간초과.

이후 우선순위 큐를 이용한 다익스트라로 해결.

 

---

아이디어

다익스트라 알고리즘은

1 -> 2 -> 3-> 4 그래프에서

1번에서 4번까지의 최단경로는 1번에서 2번, 2번에서 3번, 3번에서 4번까지의 최단경로를 포함한다는것을 전제로한다.

즉 최단경로 + 최단경로 = 최단경로다.

정점을 이동할때마다 최단경로를 계속 누적시켜주면 된다.

여기에 우선순위큐를 이용하게 되면

경로 중 최단경로를 우선적으로 탐색하여 탐색횟수를 줄일 수 있다.

 

---

구현

우선순위 큐를 이용한 성공한 구현

// c++

#pragma warning (disable : 4996)

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <cstdio>

using namespace std;

int node[20001];
int V, E, start;
vector<pair<int, int>>g[20001];

void input() {
	cin >> V >> E >> start;
	for (int i = 0; i < E; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		g[u].push_back({ w,v });
	}
}

void shortestPath() {
	memset(node, 0x7f, sizeof(node));
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
	pq.push({ 0, start });
	node[start] = 0;
	while (!pq.empty()) {
		int first = pq.top().first;
		int second = pq.top().second;
		int gSize = g[second].size();
		pq.pop();
		for (int i = 0; i < gSize; i++) {
			int nextFirst = g[second][i].first;
			int nextSecond = g[second][i].second;
			if (first + nextFirst < node[nextSecond]) {
				node[nextSecond] = first + nextFirst;
				pq.push({ first + nextFirst, nextSecond });
			}
		}
	}
}

int main() {
	input();
	shortestPath();
	for (int i = 1; i <= V; i++) {
		if (node[i] == 0x7f7f7f7f) cout << "INF" << endl;
		else cout << node[i] << endl;
	}
}

 

시간초과로 실패한 구현

//c++

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

int node[20001];
int V, E, start;
vector<pair<int, int>>g[20001];

void input() {
	cin >> V >> E >> start;
	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({ v,w });
	}
}

void shortestPath() {
	memset(node, 0x7f, sizeof(node));
	queue<int>q;
	q.push(start);
	node[start] = 0;
	while (!q.empty()) {
		int u = q.front();
		int gSize = g[u].size();
		q.pop();
		for (int i = 0; i < gSize; i++) {
			int v = g[u][i].first;
			int w = g[u][i].second;
			if (node[u] + w < node[v]) {
				q.push(v);
				node[v] = node[u] + w;
			}
		}
	}
}

int main() {
	input();
	shortestPath();
	for (int i = 1; i <= V; i++) {
		if (node[i] == 0x7f7f7f7f) cout << "INF" << endl;
		else cout << node[i] << endl;
	}
}