Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- Transport layer
- Database
- 릿코드
- 부트시퀀스
- DB
- baekjoon
- boot sequence
- BHS
- swea
- Application Layer
- 데이터베이스
- 네트워크
- 백준
- 응용 계층
- 전송 계층
- BST
- 자료구조
- C++
- STL
- dp
- Djikstra
- leetcode
- 문제풀이
- Network
- 관계형 모델
- ps
- Embedded
- 프로그래머스
- 임베디드
- 다익스트라
Archives
- Today
- Total
BOBO's Note
[ Baekjoon ] 1753. 최단 거리 본문
https://www.acmicpc.net/problem/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);
}
}
전체 코드는 여기서 확인할 수 있다.
'Algorithm > Problem Solving' 카테고리의 다른 글
[ Baekjoon ] 17837. 새로운 게임2 (0) | 2020.05.31 |
---|---|
[ Baekjoon ] 5373. 큐빙 (0) | 2020.05.31 |
[ Baekjoon ] 10217. KCM Travel (0) | 2020.05.28 |
[ Baekjoon ] 3190. 뱀 (1) | 2020.05.23 |
[ Baekjoon ] 17140. 이차원 배열과 연산 (0) | 2020.05.23 |
Comments