https://www.acmicpc.net/problem/13911
13911번: 집 구하기
첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사
www.acmicpc.net
간략하게 요약하면 임의의 정점에서 서로 다른 두 정점까지의 거리의 최솟값을 구하는 문제이다.
모든 맥도날드와 스타벅스 정점에서 다익스트라를 실행하면 TLE가 나기 때문에 다른 방법을 구사해야 한다.
핵심은 다음과 같다.
맥도날드에 이어진 가상의 정점과,
스타벅스에 이어진 가상의 정점을 생성하고 가중치가 0인 간선으로 연결하는 것이다.
이 예제에서 N + 1(9) 번 정점을 만들어서
9 -> 1
9 -> 5
간선을 가중치가 0인 간선으로 연결해보자.
또한 N + 2(10) 번 정점을 만들어서
10 -> 8
간선을 가중치가 0인 간선으로 연결해보자.
이렇게 하면 모든 맥도날드에서 각 정점에 도달하는 최단 거리와 모든 스타벅스에서 각 정점에 도달하는 최단 거리를 구할 수 있다.
즉, 많은 맥도날드와 많은 스타벅스 정점을 각각 하나의 정점으로 처리하는 테크닉을 구사한 것이다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<pair<int, int>>> v;
vector<int> mac, star;
int n, e, mc, md, sc, sd;
int house[10001];
vector<int> dijk(int start)
{
vector<int> dis(n + 3, 987654321);
priority_queue<pair<int, int>> pq;
pq.push({0, start});
dis[start] = 0;
while (!pq.empty())
{
int node = pq.top().second;
int cost = -pq.top().first;
pq.pop();
if (dis[node] < cost)
{
continue;
}
for (auto &i : v[node])
{
int nxCost = cost + i.second;
if (dis[i.first] > nxCost)
{
dis[i.first] = nxCost;
pq.push({-nxCost, i.first});
}
}
}
return dis;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> e;
v.resize(n + 3);
for (int i = 0; i < e; i++)
{
int a, b, c;
cin >> a >> b >> c;
v[a].push_back({b, c});
v[b].push_back({a, c});
}
cin >> mc >> md;
for (int i = 0; i < mc; i++)
{
int a;
cin >> a;
house[a] = -1;
v[n + 1].push_back({a, 0});
}
cin >> sc >> sd;
for (int i = 0; i < sc; i++)
{
int a;
cin >> a;
house[a] = -1;
v[n + 2].push_back({a, 0});
}
vector<int> mDis = dijk(n + 1);
vector<int> sDis = dijk(n + 2);
int ans = 987654321;
for (int i = 1; i <= n; i++)
{
if (house[i] == -1)
{
continue;
}
if (mDis[i] <= md && sDis[i] <= sd)
{
ans = min(ans, mDis[i] + sDis[i]);
}
}
if (ans == 987654321)
{
cout << -1;
}
else
{
cout << ans;
}
}
'ps' 카테고리의 다른 글
[백준] 1477 - 휴게소 세우기 (0) | 2022.11.11 |
---|---|
[백준] 3079 - 입국심사 (0) | 2022.11.08 |
[백준] 15565 - 귀여운 라이언 (0) | 2022.11.05 |
[백준] 14400 - 편의점 2 (0) | 2022.11.05 |
[백준] 20665 - 독서실 거리두기 (0) | 2022.11.04 |
댓글