1. 한 바퀴 돌린다.
2. 한 바퀴 더 돌리면서는 업데이트 될 때마다, 무한대로 설정한다.
3. 그걸로 출력
| BOJ 백준온라인져지 4963 섬의 개수 풀이 (0) | 2018.02.13 |
|---|---|
| BOJ 백준온라인져지 11004 K번째 수 풀이 (0) | 2018.02.10 |
| BOJ 백준온라인져지 1865 웜홀 풀이 (0) | 2018.02.06 |
| BOJ 백준온라인져지 1613 역사 풀이 (0) | 2018.02.03 |
| BOJ 백준온라인져지 10159 저울 풀이 (0) | 2018.02.01 |
다익스트라 알고리즘과 차이점
1. 음수 가중치가 있어도 작동이 된다.
2. 음수 사이클을 체크할 수 있다.
내가 작성한 코드의 worst time complexity 예상 O(V^2*E)
작동방식
1. distance 를 모두 임의의 값으로 체운다.
2. edge 에 가중치들을 넣는다.
3. vertex 만큼 forloop 을 하나 돌린다.
4. 그 안에서 연결된 edge 를 다 체크해준다.
5. cnt 가 N 이 된다는 것은 update 가 된다는 뜻 ( 음수 사이클 )
| BOJ 백준온라인져지 11004 K번째 수 풀이 (0) | 2018.02.10 |
|---|---|
| BOJ 백준온라인져지 1219 오민식의 고민 풀이 (0) | 2018.02.08 |
| BOJ 백준온라인져지 1613 역사 풀이 (0) | 2018.02.03 |
| BOJ 백준온라인져지 10159 저울 풀이 (0) | 2018.02.01 |
| BOJ 백준온라인져지 1389 케빈 베이컨의 6단계 법칙 풀이 (0) | 2018.01.30 |
DP로 풀었다. 계단문제랑 비슷하다.
처음에는 그냥 3나눠지면 3하고 2되면 2하고 했는데, 그게 아니라 경우의수가 최소일 때 를 구하는것 이였다.
그래서 메모이제이션이랑 Stack을 이용해서 경로구하는거 까지 구현했다.
| BOJ 2042 구간 합 구하기 풀이 (0) | 2017.10.24 |
|---|---|
| BOJ 2589 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 3번) (0) | 2017.10.23 |
| 2611 자동차경주 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 5번) (0) | 2017.10.20 |
| BOJ 2016 풀이 2004 (한국정보올림피아드시․도지역본선) (0) | 2017.10.19 |
| BOJ 11657 타임머신 풀이 벨만 포드 (0) | 2017.10.19 |
벨만포드는 다익스트라보다 느리고, 비슷하다.
다익스트라랑 다른 점은 음수가중치가 존재해도 사용이 가능하다는 것이다.
그런데 다익스트라보다 시간복잡도가 O(VE)로 크다. 다익스트라는 O(ElgV)
| 2611 자동차경주 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 5번) (0) | 2017.10.20 |
|---|---|
| BOJ 2016 풀이 2004 (한국정보올림피아드시․도지역본선) (0) | 2017.10.19 |
| BOJ 14852 타일채우기 3 풀이 (0) | 2017.10.18 |
| BOJ 2309 일곱난쟁이 풀이 (0) | 2017.10.18 |
| BOJ 2065 줄 세우기 (0) | 2017.10.18 |