백준 문제 1753번 최단경로 문제풀이 c++

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

문제해석

 

 

다익스트라 문제이다.

그런데 정점의 개수가 20000개라서 n^2 다익스트라로 구현하면 시간초과가 난다.

그래서 현재 상태에서 가장 가까운 정점을 구하는것을 우선순위큐로 구현하면 시간 초과를 피할수있다.

 

다익스트라를 실행하고 처음 d배열을 세팅할때 그리고 지금까지의 거리보다 거쳐서 가는 길이 더 최단인경우에 우선순위 큐에 그 정보를 푸쉬해주면된다.

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 999999999
using namespace std;
int getsmall();
void dijk(int start);
bool visited[20001];
int d[20001];
priority_queue < pair<int,int> > pq;
vector <pair<int,int>> vec[20001];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int V,E,K,u,v,w;
    cin>>V>>E>>K;
    for(int i=0; i<E; i++)
    {
        cin>>u>>v>>w;
        vec[u].push_back({w,v});
    }
    dijk(K);
    for(int i=1; i<=V; i++)
    {
        if(K==i)
        {
            cout<<"0\n";
        }
        else
        {
            if(d[i]==INF)
            {
                cout<<"INF\n";
            }
            else
            {
                cout<<d[i]<<"\n";
            }
        }
    }
}
int getsmall(){
    int index=0;
    while(!pq.empty())
    {
        index=pq.top().second;
        pq.pop();
        if(visited[index]==0)
        {
            return index;
        }
    }
    return index;
}
void dijk(int start){
    int v,w;
    for(int i=0; i<20001; i++)
    {
        if(start==i)
        {
            d[i]=0;
        }
        else
        {
            d[i]=INF;
        }
    }
    for(int i=0; i<vec[start].size(); i++)
    {
        w=vec[start][i].first;
        v=vec[start][i].second;
        d[v]=min(d[v],w);
    }
    visited[start]=1;
    for(int i=0; i<20001; i++)
    {
        pq.push({-d[i],i});
    }
    for(int i=0; i<20001; i++)
    {
        int cur=getsmall();
        visited[cur]=1;
        for(int j=0; j<vec[cur].size(); j++)
        {
            w=vec[cur][j].first;
            v=vec[cur][j].second;
            if(visited[v]==0&&d[cur]+w<d[v])
            {
                d[v]=d[cur]+w;
                pq.push({-d[v],v});
            }
        }
    }
}