제가 파이썬 유저라서 정확하지는 않지만 도움이 될 정보 남겨드립니다.
정점 번호가 5000 이하이고, 간선 길이가 최대 10000 이므로 (u,c) pair를 (u << 14 | c)로 저장하면 int 자료형에 간선 정보를 담을 수 있고 100MB를 사용하게 됩니다. 이러면 메모리 초과는 아마 해결될 것입니다.
그래도 시간초과가 난다면, 간선의 최대 길이를 L이라고 했을때, O(NL+T)에 최단 경로를 구하는 Dial algorithm이라는 것이 있습니다. 이것을 공부해 보는것도 좋을것 같습니다.

mintuchel 8달 전
다익스트라 문제인데 간선 갯수가 2500만개여서 시간초과랑 메모리초과 뜨는거 같아요.
vector<vector<int>> graph(SIZE)로 저장하기int graph[SIZE][SIZE]2차원 배열로 저장하기어떤 식으로 해야 시간초과와 메모리초과가 나지 않을까요??
두 방법으로 하니 안되네요.