백준 1916 - 최소비용 구하기

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

1916번: 최소비용 구하기

문제 설명

---

N의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다.

A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다.  

A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라.

도시의 번호는 1부터 N까지이다.

 

 

접근 방법

---

전형적인 Dijkstra 방식의 문제이므로 Dijkstra로 접근한다.

 

 

 

코드

---

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

using namespace std;
int n,m;
int weight[1001];
priority_queue<int,vector<int> > pq;
vector<pair<int,int> >route[1001];
void dijkstra(int start){
    pq.push(start);
    weight[start]=0;
    while(!pq.empty()){
        int num= pq.top();
        pq.pop();
        for(int i=0;i<route[num].size();i++){
            if(weight[num]+route[num][i].first<weight[route[num][i].second] ){
                weight[route[num][i].second]=weight[num]+route[num][i].first;
                pq.push(route[num][i].second);
            }
        }
    }
    
}
int main(){
    cin>>n>>m;
    memset(weight,100000001,sizeof(weight));
    for(int i=0;i<m;i++){
        int start,end,cost;
        cin>>start>>end>>cost;
        route[start].push_back(make_pair(cost,end));
    }
    int start_point,end_point;
    cin>>start_point>>end_point;
    dijkstra(start_point);
    cout<<weight[end_point]<<"\n";
    return 0;
}


//================================another=================================

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
const int INF = 987654321;
using namespace std;
int n,m;
vector<pair<int,int> >route[1001];
priority_queue<pair<int,int> >pq;

vector<int> dijkstra(int start,int end){
    vector<int> distance(end, INF);
    distance[start]=0;
    pq.push(make_pair(distance[start],start));
    while(!pq.empty()){
        int cost = -pq.top().first;
        int vertex = pq.top().second;
        pq.pop();
        if (distance[vertex] < cost) continue;
        for(int i=0;i<route[vertex].size();i++){
            int neigh = route[vertex][i].first;
            int neigh_cost = cost+ route[vertex][i].second;
            if(distance[neigh]>neigh_cost){
                distance[neigh]=neigh_cost;
                pq.push(make_pair(-neigh_cost,neigh));

            }
        }
    }
    return distance;
}
int main(){
    cin>>n>>m;
    n++;
    for(int i=0;i<m;i++){
        int sp,ep,cost;
        cin>>sp>>ep>>cost;
        route[sp].push_back(make_pair(ep,cost));
    }
    int start,end;
    cin>>start>>end;
    vector<int> ans=dijkstra(start,n);
    cout<<ans[end]<<"\n";
    return 0;
}

 

funny algorithms :0 ~