[백준/BOJ] 백준 12930번 : 두 가중치

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

12930번: 두 가중치

 

간선마다 두 개의 가중치가 있으므로, 어떤 정점에서의 지금까지 가중치 1의 합 또는 가중치 2의 합이 지금까지 해당 정점에서 가중치 1의 합 또는 가중치 2의 합보다 작은 경우(앞으로 최솟값을 만들 가능성이 있는 경우)에만 우선순위 큐에 넣는 다익스트라 알고리즘을 이용하여 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <tuple>
using namespace std;

int n;
vector<pair<int, int>> adj1[25];
vector<pair<int, int>> adj2[25];

int Solve(int start, int dest) {

	vector<int> short_w1(25, 987654321);
	vector<int> short_w2(25, 987654321);
	priority_queue<tuple<int, int, int, int>> pq; //(-현재까지 비용, 현재위치, 가중치1합, 가중치2합)

	short_w1[start] = 0;
	short_w2[start] = 0;
	pq.push(make_tuple(-0, start, 0, 0));

	while (!pq.empty()) {
		int here_cost = -get<0>(pq.top());
		int here = get<1>(pq.top());
		int here_w1 = get<2>(pq.top());
		int here_w2 = get<3>(pq.top());
		pq.pop();

		if (here == dest) {
			return here_cost;
		}

		if (here_w1 > short_w1[here] && here_w2 > short_w2[here])
			continue;

		for (int i = 0; i < adj1[here].size(); i++) {
			int there = adj1[here][i].second;
			int there_w1 = here_w1 + adj1[here][i].first;
			int there_w2 = here_w2 + adj2[here][i].first;
			int there_cost = there_w1 * there_w2;

			//하나의 가중치라도 현재까지 최소보다 작은 경우일때 (최솟값을 만들 수 있는 가능성이 있는경우)
			if (there_w1 < short_w1[there] || there_w2 < short_w2[there]) {
				short_w1[there] = min(short_w1[there], there_w1);
				short_w2[there] = min(short_w2[there], there_w2);
				pq.push(make_tuple(-there_cost, there, there_w1, there_w2));
			}

		}

	}

	return -1;
}

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;

		for (int j = 0; j < n; j++) {
			if (input[j] == '.')
				continue;

			int cost = input[j] - '0';
			adj1[i].push_back(make_pair(cost, j));
		}
	}

	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;

		for (int j = 0; j < n; j++) {
			if (input[j] == '.')
				continue;

			int cost = input[j] - '0';
			adj2[i].push_back(make_pair(cost, j));
		}
	}

	cout << Solve(0, 1);

	return 0;
}