c++ dijkstra로 풀 때 vector<pair<int,int>> adj[1010]과 같이 출발 정점에서 연결된 모든 정점들을 저장하는 경우( 1->2, 1->3 이면 adj[1] = {2,3} )

시간초과가 날 수 있습니다.

이는 출발 정점과 도착 정점이 같은 경우가 입력으로 들어오는데, 그러면 dijkstra 알고리즘을 시행하는 과정에서 같은 정점이 priority_queue에 여러 번 들어갈 수 있습니다.

이를 방지하려면 adj배열을 cost로 오름차순 정렬하면 됩니다. cost가 가장 작은 것부터 들어가면 출발 정점과 도착 정점이 같은 경우에도 도착 정점에 대한 갱신이 한 번 일어나기에(while loop한 번 동안) 같은 정점이 priority_queue에 여러번 들어가는 것을 방지합니다.