dh0450   4년 전

xy 경로에 대해서는 각 축에 대해서 정렬을 돌려 인접 정점 간의 간선만 사용하면 다익스트라로 최단거리가 나오지 않을까 생각합니다.

이때 z 경로도 같이 넣어서 다익스트라를 돌리면 편할 것 같은데

 k 가 n 보다 매우 작은 3, 4  이런 수이면 한 정점에서 z 경로를 타고 움직일 수 있는 경우의 수가 매우 많아집니다. 즉 간선의 갯수가 N^2 에 가까워집니다.

그래서 z 를 어떻게 처리해야할지 매우 난감한데, 힌트좀 주세요 ㅠㅠㅠ

pill27211   4년 전

x, y간선은 말씀하신 데로 인접 정점끼리만 처리하시면 되고, z간선은 이른 바 하이퍼 튜브(?)를 적용하셔야 합니다.

https://www.acmicpc.net/proble...

정점별로 K로 나눈 나머지값에 따라 가상의 정점을 만들어 줍니다.(기존 정점과 상관 없도록 N + 1, N + 2, ... 과 같이 해두는 게 편해요)

간선은 임의의 정점 o를 K로 나눈 나머지를 d1이라 할 때 o에서 가상의 정점 N + 1 + d1 로 향하는 가중치 z(o)간선,

역으로 K - d1를 K로 나눈 나머지를 d2라 할 때 가상의 정점 N + 1 + d2에서 정점 o로 향하는 가중치 z(o) 간선

이렇게 세팅해 주시면 됩니다.

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