[백준 1753] 최단경로

인접행렬 안됩니다. 다익스트라만 안됩니다. PQ 써야됨

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

1753번: 최단경로

#include <cstdio>
#include <cstring>
#include <queue>
#include <list>
int V, E;	// 정점의 개수, 간선의 개수
int K;		// 시작 정점의 번호

struct _st
{
	int n;
	int w;
};

struct COMP
{
	bool operator()(const _st &a, const _st &b) {
		return a.w > b.w;
	}
};

std::list<_st> L[20000 + 2];
std::priority_queue<_st, std::vector<_st>, COMP> PQ;
int nodes[20000 + 2];

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


void get_dist()
{
	// init
	for (int i = 1; i <= V; i++) {
		nodes[i] = 0x7fffffff;
	}
	PQ = {};

	PQ.push({K, 0});
	nodes[K] = 0;

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		for (_st next : L[data.n]) {
			int nn = next.n;
			int nw = data.w + next.w;

			if (nodes[nn] <= nw) continue;
			PQ.push({ nn, nw });
			nodes[nn] = nw;
		}
	}
}

void output()
{
	for (int n = 1; n <= V; n++) {
		if (nodes[n] == 0x7fffffff) printf("INF\n");
		else printf("%d\n", nodes[n]);
	}
}



int main()
{
	input();
	get_dist();
	output();
	return 0;
}

1. 처음에 인접행렬 만들어서 cost 빨리 가져오려다가 메모리 초과 났다. 

아무래도 20000 * 20000 배열이라서 그런 것 같다. 

 

2. 인접 리스트는 메모리 초과 안나겠지 하고 구현했는데 타임아웃 났다. 

노드가 20000개라서 그런 것 같다. 

 

3. 인접 리스트 + 우선순위 큐(현재 노드에서 가중치가 가장 적은 노드로 우선적으로 향한다)로 구현해야 한다.