1219번 - 오민식의 고민
검색하면서 반례를 찾긴 찾았습니다!!
3 0 2 4
0 1 9999
1 2 9999
1 1 9999
0 2 0
10000 10000 10000
Gee
출처: http://stack07142.tistory.com/273 [Hello World]
제 코드에서는 20000으로 출력하네요 ㅠㅠ
해결했습니다!!
http://stack07142.tistory.com/... 천천히 읽어보면서 공부했고..
3 0 2 4
0 1 9999
1 2 9999
1 1 9999
0 2 0
10000 10000 10000
Gee
같은 예제 에서 end까지 가는 두경로 (한개는 무한대, 한개는 유한한수) 가 있을때
무한히 증가하는 경로의 값을 LONG_MAX로 박아두면 다음 벨만포드 검사할때
dist[to] < dist[from] + cost 이부분 을 검사할 필요가 없어지네요!!
이 문제 덕분에 벨만 포드와 그래프 문제에 대해 많은거 배우고 갑니다 ㅠㅠ 저는 아직 부족하네요
댓글을 작성하려면 로그인해야 합니다.
nlkey2022 6년 전
1. BFS를 사용해서 해당 end에 도달하지 못하면 gg
2. 음수 사이클에 end가 들어있으면 Gee
3. 나머지는 최단거리 출력
어떤 반례가 있을가요?