1453 - 최단경로

첫번째 풀이

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

int graph[20001][20001];
int V, E, start;
int dist[20001];

void dijkstra() {
	priority_queue< pair< int, int >> pq;
	for (int i = 1; i <=V ; i++) {
		dist[i] = 11;
	}
	dist[start] = 0;
	pq.push({ 0,start });

	while (!pq.empty()) {
		int cur_dist = -pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();

		for (int i = 1; i <= V; i++) {
			int next_dist = cur_dist + graph[cur_node][i];
			if (dist[i] > next_dist) {
				dist[i] = next_dist;
				pq.push({ -next_dist,i });
			}
		}
	}
}

int main() {
	memset(graph, 11, sizeof(graph));
	cin >> V >> E;
	cin >> start;
	int u = 0, v = 0, w = 0;
	for (int i = 0; i < E; i++) {
		cin >> u >> v >> w;
		graph[u][v] = w;
	}
	dijkstra();
	for (int i = 1; i <= V; i++) {
		if (dist[i] == 11) {
			cout << "INF" << '\n';
		}
		else {
			cout << dist[i] << '\n';
		}
	}
	return 0;
}

시간초과!

1. 메모리를 계산해보니 20001x20001x4byte=1525MB가 문제에서 주어진 256MB를 초과해서 일어난 일이다.
   적은 메모리를 사용하여 문제를 푸려면 위의 내용처럼 인접행렬이 아닌 벡터를 이용한 인접 리스트로 이용하여 문제를 해결해야 메모리를 줄일 수 있다.

2. w의 최댓값을 11이 아닌 더 큰수로 바꿔줬다. INF=987654321

---

두번째 풀이

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

using namespace std;
#define INF 987654321

vector<pair<int, int>> graph[20001];
int V, E, start;
int dist[20001];

void dijkstra() {
	priority_queue< pair< int, int >> pq;
	for (int i = 1; i <=V ; i++) {
		dist[i] = INF;
	}
	dist[start] = 0;
	pq.push({ 0,start });

	while (!pq.empty()) {
		int cur_dist = -pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();

		for (int i = 0; i < graph[cur_node].size(); i++) {
			int next_node = graph[cur_node][i].first;
			int next_dist = cur_dist + graph[cur_node][i].second;
			if (dist[next_node] > next_dist) {
				dist[next_node] = next_dist;
				pq.push({ -next_dist,next_node });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> V >> E;
	cin >> start;
	int u = 0, v = 0, w = 0;
	for (int i = 0; i < E; i++) {
		cin >> u >> v >> w;
		graph[u].push_back({v,w});
	}
	dijkstra();
	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF) {
			cout << "INF" << '\n';
		}
		else {
			cout << dist[i] << '\n';
		}
	}
	return 0;
}