https://www.acmicpc.net/problem/25619
문제요약
- 양방향 그래프
- 기대값, 중복 방문 가능, 음수 가능
- 1번 노드에서 T 시간 이하로 갈 수 있는 노드 구하기
접근법
- 기대값 계산을 위해 2를 곱했다 치고 계산함
- dijkstra를 이용해서 최단 거리를 구하는데
- 이미 최단거리 계산을 끝낸 곳을 또 방문했다면? => 음의 사이클이 존재한다는 의미 => 무한정방문하면 무한정 줄어들 것임
- 저런 노드에서 갈 수 있는 곳은 모두 T 시간 이하로 갈 수 있을 것임
newbieski