BOJ_1916 / C++

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

1916번: 최소비용 구하기

백준 1916번 문제입니다.

다익스트라 알고리즘을 이용해서 문제를 풀었습니다.

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

#define MAX 1001
#define INF 987654321

using namespace std;

int N,M, s,d,v;

vector<pair<int,int>>connect[MAX];
int val[MAX];
int node[MAX];

void Init(int a){
	for(int i = 1; i<=a;i++)
	{
		node[i] = INF;
	}
}

void Input(){
	cin >> N >> M;
	while(M--)
	{
		cin >> s >> d >> v;
		connect[s].push_back(make_pair(d,v));
	}
	cin >> s >> d;
	Init(N);

}

void dijkstra(int start)
{
	node[start] = 0;
	priority_queue<pair<int,int>>q;
	q.push(make_pair(0,start));

	while(!q.empty())
	{
		int current_dist = -q.top().first;
		int current = q.top().second;
		q.pop();
		if(current_dist	> node[current]) continue;

		for(int i=0; i<connect[current].size() ; i++)
		{
			int next = connect[current][i].first;
			int next_dist = current_dist + connect[current][i].second;


			if(node[next] > next_dist)
			{
				node[next] = next_dist;
				q.push(make_pair(-next_dist, next));
			}
 		}
	}
}

int main(void)
{
	Input();
	dijkstra(s);
	cout << node[d];
}

도시와 거리그래프를 받아서 시작점에서 도착점까지의 최소 거리를 출력하는 문제입니다.

우선 큐에 다음 조사 노드를 넣을때 -부호를 붙이는 이유는 priority_queue의 defult는 내림차순인 것을 이용해서 가중치가 거리가 작은 노드순으로 정렬 목적입니다.

 

문제해결도중 만난 어려움은 없었고,

다익스트라 알고리즘을 응용해보기전 복습해보는 문제라고 생각됩니다.