mintuchel   8달 전

다익스트라 문제인데 간선 갯수가 2500만개여서 시간초과랑 메모리초과 뜨는거 같아요.

  1. 간선을 vector<vector<int>> graph(SIZE)로 저장하기
    1. 시점-종점이 중복되는 간선이 여러개 저장됨
    2. 메모리초과 발생
  2. 간선을 int graph[SIZE][SIZE] 2차원 배열로 저장하기
    1. 간선 조회할때 N번 탐색해야함 
    2. 시간초과발생

어떤 식으로 해야 시간초과와 메모리초과가 나지 않을까요??

두 방법으로 하니 안되네요.

oh040411   8달 전

제가 파이썬 유저라서 정확하지는 않지만 도움이 될 정보 남겨드립니다.

정점 번호가 5000 이하이고, 간선 길이가 최대 10000 이므로 (u,c) pair를 (u << 14 | c)로 저장하면 int 자료형에 간선 정보를 담을 수 있고 100MB를 사용하게 됩니다. 이러면 메모리 초과는 아마 해결될 것입니다.

그래도 시간초과가 난다면, 간선의 최대 길이를 L이라고 했을때, O(NL+T)에 최단 경로를 구하는 Dial algorithm이라는 것이 있습니다. 이것을 공부해 보는것도 좋을것 같습니다.

not_strober   8달 전

인접 리스트 + pq 다익스트라는 시간과 메모리 면에서 모두 어렵습니다. 저는 두 번째로 말씀하신 O(N2) 다익스트라로 통과했는데 cin, cout보다 빠른 입출력을 사용해야 했습니다.

바이트 스트림을 1MB씩 버퍼 용도의 buf 배열에 담은 뒤 파싱하면 됩니다. Scan의 로직은 모든 입력이 음이 아닌 정수이기 때문에 사용 가능한 방법입니다.

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