[ Baekjoon ] 1753. 최단 거리

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

1753번: 최단경로

풀이방법

다익스트라 알고리즘을 이용해 풀 수 있다. priority queue로 다음 vertex를 고르지 않으면 시간 초과가 발생한다.

 

두 vertex 사이에 여러 간선이 존재할 수 있으므로, 그 중 가중치가 최소인 간선만 저장하기 위해 adjacency list를 unordered_map을 이용해 변형했다. 각 vertex는 unordered_map을 갖는데, unordered_map은 key를 vertex로 value를 가중치로 갖는다. 간선을 입력받을 때, 해당 간선이 이미 존재하는지 O(1)의 시간으로 확인할 수 있다.

unordered_map<int, int>* adj;

adj = new unordered_map<int, int> [V]; // (vertex, weight)
int u, v, w;
for(int i=0; i<E; i++){
	scanf("%d %d %d", &u, &v, &w);
	if(adj[u-1].find(v-1) == adj[u-1].end()){
		adj[u-1].insert({v-1, w});
	}
	else{
		adj[u-1][v-1] = min(adj[u-1][v-1], w);
	}
}

 

전체 코드는 여기서 확인할 수 있다.