void Dijkstra(int start) {
while(!pq.empty()) {
int s = pq.top().second;
int w = pq.top().first;
pq.pop();
visited[s] = true;

for ( int i = 0 ; i < graph[s].size(); i++ ) {
if(visited[graph[s][i].first])
continue;
if ( dist[graph[s][i].first] > dist[s] + graph[s][i].second) {
dist[graph[s][i].first] = dist[s] + graph[s][i].second;
pq.push({dist[graph[s][i].first],graph[s][i].first});
}
}
}
}


정점 V1에서 V2로 가는 가중치가 1만이고 V1-V3-V2 로 가면 가중치가 100이라고 했을때


1. V1에서 출발하면 처음에 {1만, V2} 가 pq에 들어감.
2. 이후에 V1-V3-V2 경로 때문에 pq에 {100,v2} 가 들어감.
3. 다익스트라에서 pq가 가중치가 작은거부터 뽑으니까 {100,v2} 가 먼저 뽑히고 for문을 실행함

4. 이후에 언젠가 {1만,v2} 도 뽑히게 됨

5. 어차피 v2에서 계산되는 최단거리는 3번에서 계산됐으므로 for문 안에 첫번째 if문에서 다 빠꾸 당할 것임


질문은pq에서 정점을 뽑은 후에 만약 그 정점이 이미 방문처리가 되었으면 걍 continue를 해도 되는 건지 궁금함
아래처럼 visited[s] = true 앞에 if(visited[s]) continue; 를 넣어도 오류없이 시간 단축이 되는지..

void Dijkstra(int start) {
while(!pq.empty()) {
int s = pq.top().second;
int w = pq.top().first;
pq.pop();
if(visited[s]) continue;
visited[s] = true;

for ( int i = 0 ; i < graph[s].size(); i++ ) { // first = 도착정점 , second 가중치
if(visited[graph[s][i].first])
continue;
if ( dist[graph[s][i].first] > dist[s] + graph[s][i].second) {
dist[graph[s][i].first] = dist[s] + graph[s][i].second;
pq.push({dist[graph[s][i].first],graph[s][i].first});
}
}
}
}