[백준 1753] 알고리즘 90일차 : 최단경로

www.acmicpc.net/problem/1753

1753번: 최단경로

C++ 다익스트라

문제가 간결한 것에 비해 걸린 시간이 매우 김. 역시 골드는 만만하게 봐선 안돼

우선순위큐를 사용해서 다익스트라로 풀이하는 문제입니다.

 

접근방법

인접행렬을 사용했고, 우선순위큐를 사용했습니다.

방문 여부는 큐에서 뽑은 거리가 이미 그 노드까지의 최단경로와 같다면 그 노드에 대해서는 처리하지 않고 넘어가는 식

 

오답노트

우선순위 큐 안써서 시간초과 났었음

근데 우선순위 큐 썼는데도 계속 틀렸습니다 나길래 문제는

바로..중간에 코드 고친답시고 0번째 distances배열 값을 제외하고 INF로 초기화함 : 시작노드가 늘 0이 아닌 점을 간과함

간과한건 아닌데 실수함..그리고 distance를 시작노드와의 거리로 초기화 해주는 부분도 틀린 요인이었음

큐에 시작노드가 push돼서 들어갈거라 해줄필요없음(필요없을 뿐아니라 하면 안됨)

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int distances[20001];
int INF = 222222;
vector<vector<pair<int,int>>> weights;
int V,E,start;
void dijkstra(int v){
    priority_queue<pair<int,int>> q;
    q.push(make_pair(0, v));
    while(!q.empty()){
        int minDistance = -q.top().first;
        int next = q.top().second;
        q.pop();
        if(distances[next] < minDistance){
            continue;
        }
        for(int i = 0 ; i < weights[next].size() ; i++){
            int there = weights[next][i].first;
            int ndist = weights[next][i].second;
            if(distances[there] > minDistance + ndist){
                distances[there] = minDistance + ndist;
                q.push(make_pair(-distances[there], there));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> V >> E >> start;
    start--;
    weights = vector<vector<pair<int,int>>>(V,vector<pair<int,int>>());
    
    for(int i = 0 ; i < E ; i++){
        int s,e,w;
        cin >> s >> e >> w;
        weights[s-1].push_back(make_pair(e-1, w));
    }
    for(int i = 0 ; i < V ; i++){
        distances[i] = INF;
    }
    distances[start] = 0;
    dijkstra(start);
    for(int i = 0 ; i < V ; i++){
        if(distances[i] == INF){
            cout << "INF\n";
        }else{
            cout << distances[i] << "\n";
        }
    }
    return 0;
}