[백준] 12930 두 가중치

N 개의 정점이 있고 0번에서 1번 까지의 최단거리를 구하는 문제다

이 때 가 간선은 가중치를 2개 가진다.

최단거리는 0번부터 1번 까지의 1번가중치 합 X 2번가중치 합 이다.

처음에 완탐인줄알고 백트래킹했는데 생각해보니 최악일 때 20!이다..!

문제를 푸는방법은 그냥 다익스트라를 쓰면 된다 ㅋㅋ

pq에 (가중치1의 합, 가중치2의 합)을 추가로 넣어가면 쉽게 풀 수 있다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int n, ans = 1e9;
bool check[22];
int dist[22][22][2],d[22];
vector<vector<int>> Graph;
 
int main() {
    memset(d, -1, sizeof(d));
    scanf(" %d", &n);
    Graph.resize(n);
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                char x; scanf(" %1c", &x);
                if (x == '.') continue;
                Graph[j].push_back(k);
                Graph[k].push_back(j);
                dist[j][k][i] = (x - '0');
            }
        }
    }
    priority_queue < pair<pair<int, int>, pair<int, int>>> pq;
    pq.push({ {0,0},{0,0} });
    while (!pq.empty()) {
        int here = pq.top().first.second;
        int c1 = pq.top().second.first;
        int c2 = pq.top().second.second;
        pq.pop();
        if (check[here]) continue;
        check[here] = true;
        for (int i = 0; i < Graph[here].size(); i++) {
            int next = Graph[here][i];
            int nc1 = dist[here][next][0] + c1;
            int nc2 = dist[here][next][1] + c2;
            int ncost = nc1*nc2;
            if (d[next] > ncost || d[next]==-1) {
                d[next] = ncost;
                pq.push({ {-ncost,next},{nc1,nc2} });
            }
        }
    }
    printf("%d\n", d[1]);
}