백준 1916번 최소비용 구하기 C++

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

 

다익스트라를 이용해서 해결할 수 있는 문제이다.

인접 행렬로 풀때는 같은 경로인데 다른 비용의 입력이 있을 수 있기 때문에 주의해야 한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m;

vector<vector<int64>> graph;

struct VertexCost {

	int64 vertex;
	int64 cost;

	bool operator<(const VertexCost& other) const {
		return cost < other.cost;
	}
	bool operator>(const VertexCost& other) const {
		return cost > other.cost;
	}
};

void Dijikstra(int start, int end) {

	priority_queue<VertexCost, vector<VertexCost>, greater<VertexCost>> pq;
	vector<int64> best(n + 1, INT64_MAX);

	pq.push({ start,0 });
	best[start] = 0;

	while (!pq.empty()) {

		auto curr = pq.top();
		pq.pop();

		if (best[curr.vertex] < curr.cost)
			continue;

		for (int i = 1; i <= n; i++) {

			if (graph[curr.vertex][i] == INT64_MAX)
				continue;

			int64 nextCost = best[curr.vertex] + graph[curr.vertex][i];

			if (nextCost >= best[i])
				continue;

			pq.push({ i,nextCost });
			best[i] = nextCost;
		}
	}
	cout << best[end];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	
	graph = vector<vector<int64>>(n + 1, vector<int64>(n + 1, INT64_MAX));
	for (int i = 0; i < m; i++) {
		int64 start, end, cost;
		cin >> start >> end >> cost;
		graph[start][end] = min(graph[start][end], cost);
	}
	int start, end;
	cin >> start >> end;
	Dijikstra(start, end);
};