백준 - 최소비용 구하기(1916)

간단한 다익스트라 문제이다.

c++로 풀어보았는데

그래프를 클래스로 관리하는 법으로 풀었다.

 

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <climits>

using namespace std;

struct Edge {
	int to;
	int weight;
};

class Graph
{
	private:
		vector<vector<Edge>> adj;
	public:
		Graph(int vertices) : adj(vertices){}

		void addEdge(int from, int to, int weight) {
			adj[from].push_back({to, weight});
		}

		vector<Edge> getEdges(int vertex) {
			return adj[vertex];
		}

		int size() {
			return adj.size();
		}
};

int main()
{
	int n, m;
	cin >> n;
	cin >> m;

	Graph graph(n+1);
	for (int i = 0; i < m; i++)
	{
		int from, to, weight;
		cin >> from >> to >> weight;
		graph.addEdge(from, to, weight);
	}

	int start_node, end_node;
	cin >> start_node >> end_node;


	vector<int> dist(n+1, INT_MAX);
	dist[start_node] = 0;

	priority_queue<pair<int, int>, vector <pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0, start_node });

	while (!pq.empty())
	{
		int cur_dist = pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();

		if (cur_dist > dist[cur_node]) continue;


		for (Edge edge : graph.getEdges(cur_node)) {
			int new_dist = cur_dist + edge.weight;
			int new_node = edge.to;

			if (new_dist < dist[new_node]) {
				dist[new_node] = new_dist;
				pq.push({ new_dist, new_node });
			}
		}
	}

	cout << dist[end_node];

}

Graph의 생성자로 노드의 개수를 보내면

vector<vector<Edge>>는 노드의 개수에 맞게 초기화가 된다.

그 후 from, to , weight을 입력받고 addEdge를 통해 adj벡터에 넣어준다.

getEdges를 통해 시작노드를 인덱스로 어디로 연결되어 있는지와 비용을 구할 수 있다.

 

Edge 구조체를 통해 좀 더 가시성이 좋게 표현을 해주었다.

 

 

개인 프로젝트로 인해 알고리즘에 시간투자를 못했지만

오랜만에 복습할 겸 풀어보았다.