티스토리 뷰
https://www.acmicpc.net/problem/11657
11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
Bellman Ford 알고리즘.
다익스트라와 다른점은 음의 간선이 있을수 있을때, 음의 간선이 있는지 판별 가능하다.
다익스트라는 현재 정점에서 가장 거리가 가까운 노드만을 방문하지만 벨만포드에서는 뒤에 음의 간선의 존재에 의하여 모든 간선을 탐색해야 한다.
음의 사이클이 존재하는지 확인하는 방법은 모든 간선 탐색을 N-1번 수행후 N번째 수행했을때도 갱신되는 거리가 있다면, 음의 사이클이 있다고 판단한다.
'PS' 카테고리의 다른 글
| 백준 2056. 작업 (0) | 2022.08.03 |
|---|---|
| 백준 5427. 불 (0) | 2022.08.03 |
| 백준 5582. 공통 부분 문자열 (0) | 2022.08.02 |
| 백준 1600. 말이 되고픈 원숭이 (0) | 2022.08.02 |
| 백준 1937. 욕심쟁이 판다 (0) | 2022.08.02 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- permutation
- recursion
- BFS
- DP
- graph
- priority queue
- 재귀
- db
- Spring
- greedy
- MVC
- Brute Force
- C++
- 자료구조
- Stack
- two pointer
- dfs
- C
- Tree
- CSS
- back tracking
- floyd warshall
- 이분탐색
- Unity
- 조합
- Python
- binary search
- Implementation
- Dijkstra
- Kruskal
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 | 31 |
글 보관함