문제 링크
-
문제 해결
1. 단방향 그래프를 입력받고, 1부터 N까지의 임의의 점에서 K까지의 최단거리와 K부터 임의의 점까지의 최단거리의 합 중에서 가장 큰 값을 구하는 문제.
2. 다익스트라 알고리즘으로 문제 해결.
주의할 점 || 생각해볼 점
1. 최대 간선의 수(N)가 10,000개, 최대 정점의 수(M)가 1,000개. 1부터 N까지의 임의의 수 전부에서 최단거리를 구하려면 시간복잡도 에 의해서 아슬아슬해진다. 그러므로 입력 받을 때, 정방향과 반대방향 인접리스트를 두 개 만들어서 K에서 다익스트라 알고리즘을 두 번 수행하면 된다.
참고
- 다익스트라 알고리즘 visual code : https://www.swexpertacademy.com/main/visualcode/main.do#/home/mainlayout
※ 정확하고 부드러운 태클은 언제나 환영입니다.
'Problem Solving > 그래프' 카테고리의 다른 글
BOJ 11559 - Puyo Puyo (0) | 2017.10.17 |
---|---|
BOJ 1761 - 정점들의 거리 (0) | 2017.10.06 |
codeground practice - 최소 신장 트리 (0) | 2017.07.14 |
BOJ 14502 - 연구소 (0) | 2017.07.12 |
BOJ 14621 - 나만 안되는 연애 (0) | 2017.06.29 |