1. 이 문제는 다익스트라 알고리즘을 사용해야 하는 문제입니다. 이 알고리즘에 대해 들어보지 못했다면 먼저 찾아서 공부한 뒤에 푸시는 것을 추천드립니다.
2. 벨만 포드, 플로이드 알고리즘 등은 사용할 수 없습니다. 알고리즘 문제는 단순히 답을 구하는 것만이 목적이 아니고, 그 답을 시간/메모리 측면에 대해 효율적으로 구하는 것까지도 포함합니다. 시간복잡도를 생각해 보세요. 벨만 포드는 O(VE), 플로이드는 O(V^3)으로 각각 60억, 8조에 해당하고, 컴퓨터가 초당 약 10억 회의 연산을 한다고 가정하면 각각 6초, 8000초가 소요됩니다. 또한 평균적으로 O(E)에 동작한다고 알려져 있는 SPFA 알고리즘 역시 최악의 경우는 O(VE)로 이전에 저격되었습니다. 우리는 단순하게 구현했을 때 O((V+E)logE)가 되는 다익스트라 알고리즘을 사용해야 합니다.
3. 간선 정보는 인접 행렬이 아니라 인접 리스트로 저장해야 합니다. 인접 행렬을 사용하게 되면 2만 개의 정점에 대해 2만 개 정점으로 가는 간선들을 저장해야 하는데, 간선 하나당 1바이트에 저장한다고 하더라도 4억 바이트, 약 400MB의 메모리를 쓰게 될 뿐 아니라 시간복잡도 역시 O(V^2)으로 좋지 못하게 됩니다. 어떻게든 압축하면 통과는 시킬 수 있을지도  모르겠지만, 사서 고생입니다. 현재 정점에 연결된 간선들의 번호만 리스트로 저장해서 사용하는 것이 좋습니다.
4. 다익스트라 알고리즘은 루프마다 항상 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 정점을 뽑아야 합니다. 다른 순서로 정점을 뽑는 것은 시간복잡도를 보장하지 못하거나 잘못된 답에 이르게 할 수 있습니다. 대표적으로 잘못된 순서는,
   1. 큐에 넣은 순서
   2. 정점까지의 거리가 제일 먼 것부터
   3. 간선의 가중치가 제일 작은/큰 것부터 <- 가장 많이 틀리는 부분입니다.
   4. 정점 번호가 작은/큰 순서 등이 있습니다.
5. C++에서 std::pair는 first끼리를 먼저 비교하고, first가 같으면 second를 비교합니다. 이게 무슨 뜻이냐면, pair<int, int>로 우선순위 큐에 원소를 넣는다면 반드시 first에 거리가 들어가야 한다는 뜻입니다. 정점 번호끼리의 비교에는 아무런 의미가 없습니다. 물론 직접 비교 함수를 정의해서 second를 먼저 보게 만들 수는 있습니다.
6. priority_queue는 기본적으로 가장 큰 원소부터 뽑습니다. 그래서 std::pair를 사용하면서 거리가 가장 가까운 정점부터 뽑기 위해서는,
   1. 거리에 마이너스를 붙여서 저장하거나,
   2. 사용자 정의 비교 함수를 만들어서 비교 규칙을 알려주거나,
   3. functional 헤더에 있는 greater를 이용해서 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> 등으로 사용하는 방법이 있습니다.
   4. 개인적으로는 pair를 쓰지 않고 구조체를 새로 하나 정의하는 것을 깔끔하게 생각합니다.
7. 이 문제에서는 간선의 가중치가 작아서 저격 데이터를 만들 수 없지만, 일반적으로는 우선순위 큐에서 정점을 뽑은 뒤 이미 방문한 정점이 아닌지를 반드시 체크해야 합니다. 물론 이대로 두더라도 이전에 방문했을 때 인접한 정점들에 대한 거리 갱신은 모두 끝났을 테니 다시 갱신시키는 일은 없겠지만, 문제는 그 주변의 간선들을 전부 체크하는 것 자체에 있습니다. 한 정점이 거리 갱신을 수만 번 당하면서 수만 번 우선순위 큐에 들어갔는데, 우선순위 큐에서 나올 때마다 간선을 수십만 개씩 체크하게 된다면 매우 오랜 시간이 걸리게 됩니다. 단순히 우선순위 큐에서 나온 거리가 현재 거리 배열에 저장된 값과 같은지를 비교하는 것으로 방문 체크를 할 수 있습니다.
8. INF는 항상 (간선 가중치의 최댓값) * (정점 개수 - 1) 보다 큰 값을 사용해야 합니다. 거리가 가장 멀어지는 경우를 생각해 보면, 1-2-3-4-5-6-...-V 이렇게 일직선으로 모든 간선이 최대 가중치를 가지고 연결되어 있을 때 총 V-1개의 간선을 전부 차례대로 지나가야 하기 때문입니다. 이 문제에서는 최소한 20만 이상의 INF를 사용해야 합니다.
9. 시작점은 1번이 아니고 입력으로 주어집니다.
10. 모든 정점의 거리에 대해 항상 개행 문자를 출력하세요. INF를 출력했을 때도 마찬가지입니다.
11. "서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다." 이 말이 괜히 있는 게 아닙니다. 간선이 들어올 때 두 도시 사이를 이동하는 비용을 무조건 덮어쓰면 안 됩니다. 나중에 입력된 간선의 비용이 더 크다면 어떻게 될까요?

자세한 설명은 http://www.secmem.org/blog/2019/01/09/wrong-dijkstra/ 를 참고하세요.