(백준 1916번 최소비용 구하기 / 백준 4485번 녹색 옷 입은 애가 젤다지?) 라이님 블로그 대회 알고리즘 따라잡기 16) 다익스트(Dijkstra's Algorithm)

백준 1916번

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

 

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

using namespace std;

typedef pair<int, int> P;

void dijkstra(int V, int start, int end, const vector<vector<P>>& adj) {
	vector<int> dist(V, INT_MAX);
	priority_queue<P, vector<P>, greater<P>> pq;
	dist[start] = 0;
	pq.emplace(0, start);

	while (!pq.empty()) {
		int curr_dist = pq.top().first;
		int curr = pq.top().second;
		pq.pop();

		if (dist[curr] < curr_dist) continue;

		for (const P& edge : adj[curr]) {
			int next = edge.first;
			int weight = edge.second;
			if (dist[next] > dist[curr] + weight) {
				dist[next] = dist[curr] + weight;
				pq.emplace(dist[next], next);
			}
		}
	}

	cout << dist[end];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	vector<vector<P>> adj;
	int N, M; cin >> N >> M;
	adj.resize(N);
	for (int i = 0; i < M; i++) {
		int u, v, w; cin >> u >> v >> w;
		adj[u - 1].emplace_back(v - 1, w);
	}
	int start, end; cin >> start >> end;
	start--; end--;
	dijkstra(N, start, end, adj);
	return 0;

}

 

백준 4485번

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

 

<- 다익스트라에서 그래프를 주어지는 방법이 약간 달라진 문제

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int, int> P;

bool isInside(int x, int y, int V) {
	if (x < 0 || y < 0 || x >= V || y >= V) return false;
	return true;
}
void dijkstra(int V, const vector<vector<int>> &adj) {
	int dir_x[4] = { 1, 0, -1, 0};
	int dir_y[4] = { 0, 1, 0, -1 };
	vector<int> dist(V * V, INT_MAX);
	priority_queue<P, vector<P>, greater<P>> pq;

	dist[0] = adj[0][0];
	pq.emplace(dist[0], 0);

	while (!pq.empty()) {
		int curr_dist = pq.top().first;
		int curr = pq.top().second;
		pq.pop();

		if (dist[curr] < curr_dist) continue;
		int curr_x = curr / V; //cout << "curr_x: " << curr_x << endl;
		int curr_y = curr % V; //cout << "curr_y: " << curr_y << endl;

		for (int i = 0; i < 4; i++) {
			int next_x = dir_x[i] + curr_x; 
			int next_y = dir_y[i] + curr_y; 
			int next = next_x * V + next_y;
			if (isInside(next_x, next_y, V)) {
				int weight = adj[next_x][next_y];
				if (dist[next] > dist[curr] + weight) {
				//	cout << "next_x: " << next_x << endl;
				//	cout << "next_y: " << next_y << endl;
				//	cout << "next : " << next << endl;
				//	cout << "dist[curr] : " << dist[curr] << endl;
				//	cout << "weight :" << weight << endl;
					dist[next] = dist[curr] + weight;
					pq.emplace(dist[next], next);
				}
			}
		}
	}
	cout << dist[V * V - 1];
}

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

	int V; int cnt = 1;
	while (cin >> V && V != 0) {
		vector<vector<int>> adj; 
		adj.resize(V);
		for (int i = 0; i < V; i++) adj[i].resize(V);
		
		for (int i = 0; i < V; i++) {
			for (int j = 0; j < V; j++) {
				cin >> adj[i][j];
			}
		}
		cout << "Problem " << cnt++ << ": ";
		dijkstra(V, adj);
		cout << "\n";
	}
	return 0;
}