다익스트라 알고리즘

제발..!!! 이제 기억좀 하자!!!

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

1753번: 최단경로

 

한 점 에서 다른 점으로 가는 최단거리 알고리즘

 

어떻게 써 ?

 

 - > 1. dist[ 노드 수] 만큼 모두 무한으로 설정 ( INF , 1e9)

 

-> fill 함수 사용하기! (사실 안써도 되는듯)

 

2. for문 돌리며 값 대입 v[출발노드] . push_back( 거리 , 다음노드) 

 

--> 주의 !!! 거리를 vecotor 에 앞에 나둠.

3. priority queue 선언.  -> 기존거랑 다르게 greater 붙이고 최소부터 나오는 pq 선언해야함.

 

4.pq에 pq.push({0,시작점}) 

 

5. pq가 빌때까지 돌면서 pq에서 node와 w 꺼내고, pq에 꺼낸 거리 w 가, dist[n ( 방금 꺼낸 노드)] 보다 크면 넘어감. **

    while(!pq.empty()){

        P top = pq.top(); pq.pop();

        int n = top.N;

        int w = top.W;

        if(dist[n]<w) continue; //거기까지 가는 거리가 , 그거리보다 크면 밴

6. v[ n ] 를 하나하나 돌면서, dist[ 방금꺼낸노드 ]  > dist[ n ] + 방금 꺼낸 거리 보다 크면 ( 즉, n으로 꺼낸 dist와 방금 꺼낸 dist + 거리 로 줄일 수 있다면) 

 

6-2 . 그 값으로 dist[node] 변경 , pq. push ({dist[node], node }) 넣기.

 

 

    #include <string>
#include <vector>
#include <queue>
#include <iostream>
    using namespace std;

#define P pair<int,int>
#define W first
#define N second

const int MN = 20101;
const int INF = 1e9;
    int dist[MN];
    vector <P> g[MN];
    int main(){

        int V,E,S;
        cin>>V>>E>>S;
        for(int i=0;i<E;i++){
            int u,v,w; cin>>u>>v>>w;
            g[u].push_back({w,v}); // g에는 먼저 가는 거리, 다음 갈곳 넣음
        }
        fill(dist,dist+V+1,INF);
        priority_queue<P,vector<P>,greater<P>> pq;
        pq.push({0,S});

        dist[S]=0;

        while(!pq.empty()){
            P top = pq.top(); pq.pop();
            int n = top.N;
            int w = top.W;

            if(dist[n]<w) continue; //거기까지 가는 거리가 , 그거리보다 크면 밴

            for(P edge : g[n]){
                int node = edge.N;
                int weight = edge.W;

                if(dist[node] > dist[n] + weight)
                {
                    dist[node] = dist[n] + weight;
                    pq.push({dist[node],node});
                }
            }
        }
        for(int i=1;i<=V;i++){
            dist[i]==INF ? (cout<<"INF\n") :(cout<<dist[i]<<"\n");
        }
    }