백준 1916번 최소비용 구하기

문제

N의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

 

 

다익스트라 알고리즘 : 그냥 크루스칼과 같은 최단경로 문제와 다른점은 작은 순서대로 임의로 경로를 만드는 것이 아니고 출발지가 정해져 있음. 출발 정점으로부터 나머지 정점 까지의 거리를 업데이트 하면서 초기화 하는 작업이 필요,

솔직히 dijkstra함수만 구현할 줄 알면 되는데 구현법은 우선 시작점을 기준으로 각 정점에 대한 최소 거리를 저장할 배열이 필요한데 이를 벡터로 선언해 준다. 그리고 시작점을 기준으로 시작점까지 거리는 0이니 distance[start]만 0으로 초기화 해주고 나머지 정점에 대해서는 우선 무한대로 표기,

그리고 최소힙이 필요한데 이유는 cost값이 작은 순으로 먼저 방문해서 뻗어 나가기 때문이다. 만약 최소 거리만으로 모든 정점을 다 돌 수 있다면 이보다 큰 코스트를 가진 정점을 굳이 방문할 필요는 없으니까,

우선 우선순위 큐에 cost값 0과 start정점의 인덱스를 pair로 넣어 주고, while문에서 pq가 empty()가 될때 까지 반복 시키는데 무엇을 반복 시키냐면 현재 우선순위 큐의 top 즉 기준점으로 부터 cost가 최소인 정점의 인덱스와 그 cost값을 빼온 후에 pop시킨다. 그 후 그 정점에 있어서 연결된 다음 정점에 대해 이동할 때 현재 까지의 정점들(경로)을 거쳐서 이동하는 것이 기준점으로 부터 원래의 거리보다 짧다면 distance를 업데이트 시켜준다,

현재 정점에서 다음정점으로 이동하는 것을 보기 위해서는 각 정점간의 연결 정보를 저장한 vector에서 현재 정점을 인덱스로 하는 배열의 사이즈를 보면 연결된 다음 정점들의 수가 나오고, 첫번째 정점부터 cost값과 인덱스 값을 뽑아서 다음정점을 이동하는데 현재까지의 경로값에서 추가된 값과 지금까지의 distance값을 비교해서 distance보다 짧으면 distance를 업데이트 시켜주면 된다. 그리고 이는 최단 경로가 되므로 우선순위 큐에 그 인덱스와 갱신된 cost값을 저장해주면된다. ,

간단하게 설명하면 기준점에서 기준점과 연결된 정점중 가장 짧은 경로의 정점으로 이동한후 그 정점에서 연결된 다음 정점을 봤을 때 현재 까지의 경로값에 현재정점에서 다음 정점까지의 경로를 더한 값이 지금까지 기준점으로부터 다음정점까지의 거리라고 알려진 값보다 작다면 업데이트 그리고 이는 다음 단계를 나아가는데 있어 최소 경로이므로 큐에 저장 이라고 볼 수 있다.

그리고 Int자료형으로 무한대를 표기하고 싶을때는 987654321을 사용하자

 

 

 

 

 

 

 

 

 

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

using namespace std;

const int INF = 987654321;
int V,E;
vector <pair<int,int> > vec[1001];



vector dijkstra(int start, int vertex)
{

 

vector distance<int> (vertex);

for(int i=0; i<vertex; i++)
{
distance[i] = INF;
}

distance[start]=0;

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;



pq.push({0,start});

while(!pq.empty())
{
int cost = pq.top().first;
int current = pq.top().second;
pq.pop();

 
 

for(int i=0; i<vec[current].size(); i++)
{

int nextvertex = vec[current][i].first;
    int newdistance = cost+vec[current][i].second;
    
    if(distance[nextvertex] > newdistance )
    {
     distance[nextvertex] = newdistance;
     pq.push({newdistance, nextvertex});
}


}




}

return distance;



}



int main(void)
{

cin>>V;
cin>>E;



for(int i=1; i<=E; i++)
{
int a,b,c;

cin >>a>>b>>c;

vec[a].push_back({b,c});
}

int start,end;

cin >> start >> end;

vector result;

 result = dijkstra(start,V+1);



cout<<result[end]<<endl;




}