백준 13911 - 집 구하기 (C++)

문제

• 문제 링크

  
   BOJ 13911 - 집 구하기 
  

• 문제 요약

이사 갈 지역의 지도가 그래프로 주어지고 맥도날드 및 스타벅스의 위치 정보가 주어진다.
문제에 정의된 $3$가지 조건을 만족하면서, 맥도날드 및 스타벅스까지의 거리 합이 최소가 되는 집을 찾아보자.

• 제한

TL : $1$ sec, ML : $256$ MB




$3 ≤ V ≤ 10,000$

$1 ≤ w ≤ 10,000$

$0 ≤ E ≤ 300,000$

$1 ≤ x, y ≤ 100,000,000

알고리즘 분류

• 그래프 이론(graphs)
• 다익스트라(dijkstra)

풀이

우선 다익을 이용하는 문제란 것은 쉽게 알아 챌 수 있다.
당연히 모든 집에서 다익을 돌려보는 것은 간선의 개수가 많아 $TLE$ 확정일 듯 싶다.

역으로 맥도날드, 스타벅스의 입장으로부터 생각해보자.

보통 임의의 한 지점을 우선순위 큐에 넣으면서 다익이 시작 되지만, 이번엔 모든 맥도날드( 또는 스타벅스 ) 매장이 시작점이 될 수 있다.
따라서 모든 매장을 몽땅 우선순위 큐에 넣어주고 다익을 돌려주면 총 $2$번의 다익으로 문제 해결에 필요한 모든 정보를 뽑아낼 수 있다.

$Dist[u][0]$ : $u$에서 가장 가까운 맥도날드 매장과의 거리

$Dist[u][1]$ : $u$에서 가장 가까운 스타벅스 매장과의 거리

최종적으로 답은 $Dist[u][0] ≤ x$ && $Dist[u][1] ≤ y$ 를 만족하는 $min(Dist[u][0] + Dist[u][1])$ 의 값.
단, $u$는 집이어야 한다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
vector <pair<int, int>> Gr[10001];
int v, e, x, y, r(2e9), Info[10001], Dist[10001][2];
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    fill(&Dist[0][0], &Dist[10000][2], 2e9);
    cin >> v >> e;
    for (int i, j, w; e--;)
        cin >> i >> j >> w, Gr[i].emplace_back(j, w), Gr[j].emplace_back(i, w);
    int c, i;
    for (cin >> c >> x; c--;) cin >> i, Info[i] += 1;
    for (cin >> c >> y; c--;) cin >> i, Info[i] += 2;
}
void f(int o)
{
    priority_queue <pair<int, int>> Q;
    for (int i(1); i <= v; i++)
        if (Info[i] == o || Info[i] == 3)
            Dist[i][o - 1] = 0, Q.push({ 0, i });
    for (--o; Q.size();)
    {
        auto [p, q](Q.top()); Q.pop();
        if (Dist[q][o] >= -p)
            for (auto& [a, b] : Gr[q])
                if (int k(b - p); k < Dist[a][o])
                    Dist[a][o] = k, Q.push({ -k, a });
    }
}
void Solve()
{
    f(1); f(2);
    for (int i(1); i <= v; i++)
        if (!Info[i] && Dist[i][0] <= x && Dist[i][1] <= y)
            r = min(r, Dist[i][0] + Dist[i][1]);
    cout << (r < 2e9 ? r : -1);
}
int main()
{
    Init();
    Solve();
}

comment

끝