sgc109   3달 전

단순히 플로이드로 도달가능성을 인접행렬로 구해놓고

벨만포드 에서 식을 조금 변형시켜서(도시에서 벌어들이는 수입도 같이계산)

음수 사이클이 있을경우 시작지점부터 음수사이클로 도달가능한지, 그리고 음수사이클부터 도착지점까지 도달 가능한지를

체크해서 가능해면 Gee 불가능하면 시작지점부터 도착지점까지 최단거리, 그리고 애초에 시작점에서 도착점까지 도달불가능하면 gg 를 

출력하도록 코드를 작성해서 제출을 해봤는데 22%에서 틀렸습니다. 가 뜨는데

제가 간과한 부분이 어떤건지 잘 모르겠습니다. 애초에 중요한걸 빠뜨린 걸까요?

kcm1700 조언주시면 감사드리겠습니다.

kcm1700   3달 전

나머지는 아직 자세히 안 읽어봤는데 long long이 되어야 할 것 같은데, 혹시 아닌가요

sgc109   3달 전

kcm1700 

'N과 M은 100보다 작거나 같고, 돈의 최댓값과 교통 수단의 가격은 1,000,000보다 작거나 같은 음이 아닌 정수이다.'

라는 걸보고 양수던 음수던 100*1000000 정도가 최대치라고 생각해서 int로 했는데 제가 간과한 부분이있을까요..?

kcm1700   3달 전

갱신되는 최악의 경우를 따져보시면, 루프 한 번당 100번씩 교통 수단 가격이 더해지며 돌아갈 수 있겠네요.

왜 100*1000000을 최대치라고 생각했나요?

sgc109   3달 전

kcm1700 N과 M 이 100이라 아무리 못해도 출발점에서 모든 도착점까지 100개 미만의 간선을 거쳐서 다다를수있다고 생각했고

각각의 간선은 커봐야 비용이 100만이 드니까 비용의 최대치는 1억이라고 생각했는데.. 좀더 생각해보니 1억은 모든 루프가 돌았을 때 최종적으로 있을 수 있는 upper 의 상한인것같군요..

최종적인 값이 구해지는 과정에서 아직 최단경로가 완화 되기전에 훨씬 큰 값을 찍고 단순에 완화가 될수도 있어서 그런건가요?

sgc109   3달 전

혹시 말씀하신 최악의 경우의 예를 가르쳐주실수있으신가요..? 사실 좀 이해가 잘 가지 않네요

kcm1700   3달 전

나이브하게 따져서, k 값 하나당, 100만이라는 값이 100번 더해질 수 있죠?
그리고 k가 100번 돌 수 있네요. 그러면 100만 * 100 * 100 아닌가요?

말씀하신 내용은 최단 경로가 올바르게 존재할 경우에만 적용할 수 있는 내용이네요. 그렇지 않으면 전제로 깔고 들어가신, 100개 미만의 간선만 거친다는 부분이 바르지 않네요.

실제로 그러한 경우가 있어요. 계속 갱신되는 사이클이 있는 경우입니다.


댓글을 작성하려면 로그인해야 합니다.