코딩테스트 백준 1916

이제 이직 준비 시작.

 

다익스트라를 사용한다는 점은 흔하지만 데이터 조건으로 인해 자료구조를 vector에서 배열로 바꾸고 중복 선 처리를 통해

성능 개선을 시켜줘야 통과 가능했다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int graph[1002][1002];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int dist[1001];

int main(){
    int n, m;
    int u, v, w;
    int start, end;
    
    cin>>n>>m;
    
    for(int i=1; i<=n; i++){
        
        for(int j=1; j<=n; j++){
            graph[i][j] = 999999999;
        }
    }
    
    for(int i=1; i<=n; i++){
        graph[i][i] = 0;
        dist[i] = 999999999;
    }
    
    for(int i=0; i<m; i++){
        cin>>u>>v>>w;
        if(graph[u][v] > w)
            graph[u][v] = w;
    }
    
    cin>>start>>end;
    
    dist[start] = 0;
    
    pq.push(make_pair(0, start));
    
    while(!pq.empty()){
        int weight = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        
        for(int i=1; i<=n; i++){
            int next = i;
            int nWeight = graph[cur][i];
            
            if(nWeight == 999999999)
                continue;
            
            if(weight + nWeight < dist[next]){
                dist[next] = weight + nWeight;
                pq.push(make_pair(weight+nWeight, next));
            }
        }
        
    }
    
    cout<<dist[end];
    return 0;
}