[백준 5972] 택배 배송

다익스트라 연습 문제이다.

길에서 마주치는 소를 가중치라고 보면 된다.

 

다익스트라는 양방향 그래프에서도 적용되는데 이유는 생각해보면 간단하다.

 

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
#include <climits>

#define SIZE 50001

using namespace std;

int N, M;

// <end, cost>
// arr[i]는 i노드와 연결된 경로들 vector
vector<vector<pair<int, int>>> arr(SIZE);
// <cost, end>
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
bitset<SIZE> visited;
vector<int> ans(SIZE);

int Dijkstra(int start, int end) {

	for (int i = 1; i <= N; i++) { ans[i] = INT_MAX; }

	pq.push(make_pair(0, start));
	ans[start] = 0;
	visited[start] = 1;

	while (!pq.empty()) {
		pair<int, int> cur = pq.top();
		int cost_so_far = cur.first;
		int start = cur.second;
		pq.pop();

		if (cost_so_far > ans[start]) continue;

		// pq에서 나왔다는 것은 최소값 확정이라는 뜻
		visited[start] = 1;

		for (int i = 0; i < arr[start].size(); i++) {
			pair<int, int> next = arr[start][i];
			int end = next.first;
			int cost = next.second;

			// 확정되지 않았으면 
			if (!visited[end]) {
				if (cost_so_far + cost < ans[end]) {
					ans[end] = cost_so_far + cost;
					pq.push(make_pair(cost_so_far + cost, end));
				}
			}
		}
	}
	return ans[end];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	int start, end, cows;
	for (int i = 0; i < M; i++) {
		cin >> start >> end >> cows;
        	// 양방향이므로
		arr[start].push_back(make_pair(end, cows));
		arr[end].push_back(make_pair(start, cows));
	}

	cout << Dijkstra(1, N);
	return 0;
}