[백준 1916] 최소비용 구하기

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

1916번: 최소비용 구하기

요구사항

주어진 정점까지 최소거리

 

풀이

기본 다익스트라 알고리즘

 

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

using namespace std;

struct go{
    int x;
    int y;
};
int n,m;
int dist[1001];
vector<go>v[100001];
int heap_size=0;
go heap[100001];
int qsize=0;
void push(go data){
    int target=heap_size+1;
    while(target!=1 && heap[target/2].y > data.y){
        heap[target]=heap[target/2];
        target /=2;
    }
    heap[target]=data;
    qsize++;
    heap_size++;
}
void pop(){
    int parent=1;
    int child=2;
    go temp=heap[heap_size];
    while(child<heap_size){
        if(child+1<heap_size && heap[child].y > heap[child+1].y)
            child++;
        if(temp.y<=heap[child].y)
            break;
        heap[parent]=heap[child];
        parent=child;
        child *=2;
    }
    heap[parent]=temp;
    heap_size--;
    qsize--;
}
bool com(go x, go y){
    return (x.y<y.y);
}


int main()
{

    cin>>n>>m;
    for(int i=1; i<=n; i++){
        dist[i]=987654321;
    }   
    for(int i=0 ; i < m ; i++){
        int x,y,z;
        cin>>x>>y>>z;
        v[x].push_back({y,z});
    }
    int s,c;
    cin>>s>>c;
    //priority_queue<pair<int,int>> q;
    go temp;
    temp.x=s;
    temp.y=0;
    push(temp);
    dist[s]=0;
    while(qsize!=0)
    {
        int cost = heap[1].y;
        int node = heap[1].x;
      //  cout<<cost<<" "<<node<<endl;
        pop();

        for(int i=0 ; i < v[node].size() ; i++){
            int nownode= v[node][i].x;
            int nowcost = v[node][i].y +cost;
            if(nowcost < dist[nownode]){
                dist[nownode]=nowcost;
                temp.x = nownode;
                temp.y = nowcost;
                push(temp);
            }

        }
    }
    cout<<dist[c]<<endl;


}