[BOJ] 13911. 집 구하기

*다익스트라 문제 

*시작 정점은 각 맥도날드와 스타벅스의 정점들 (시작 정점은 dist[]를 0으로 초기화하는 것을 잊으면 안된다)

*다익스트라를 두 번 실행한다. (맥도날드를 기준으로 각 집들까지의 거리 / 스타벅스를 기준으로 각 집들까지의 거리)

*dist배열을 2차원 혹은 두 개를 만들어서 함수를 실행할 때 파라미터로 보내준다. (맥도날드 / 스타벅스를 기준으로 최단거리 저장)

*다익스트라의 결과로 받아낸 dist1 , dist2 배열의 값 중 각 집에서 x, y 값 이하의 거리에 있는 맥도날드와 스타벅스까지 거리의 합의 최소가 정답이다. 

 

 

 

#include <iostream> #include <vector> #include <cstring> #include <queue> #include <functional> #define INF 987654321 #define MAXX 10001 using namespace std; typedef pair<int, int> pp; vector<pp> edges[MAXX]; int m, s; int value[MAXX]; bool visited[MAXX]; priority_queue<pp, vector<pp>, greater<pp>> q; void bfs(vector<int> &dist) { memset(visited, 0, sizeof(visited)); while (!q.empty()) { int now = q.top().second; int cost = q.top().first; q.pop(); if (visited[now]) continue; visited[now] = true; for (auto i : edges[now]) { int next = i.second; int n_cost = i.first; if (!visited[next] && dist[next] > dist[now] + n_cost) { dist[next] = dist[now] + n_cost; q.push(pp(dist[next], next)); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int v, e; cin >> v >> e; for (int i = 0; i < e; i++) { int a, b, c; cin >> a >> b >> c; edges[a].push_back(pp(c, b)); edges[b].push_back(pp(c, a)); } vector<int> dist1(v + 1, INF), dist2(v + 1, INF); int x, y; cin >> m >> x; for (int i = 0; i < m; i++) { int a; cin >> a; value[a] = 1; dist1[a] = 0; q.push(pp(0, a)); } bfs(dist1); cin >> s >> y; for (int i = 0; i < s; i++) { int a; cin >> a; value[a] = 1; dist2[a] = 0; q.push(pp(0, a)); } bfs(dist2); int ans = INF; for (int i = 1; i <=v; i++) { if (!value[i] && dist1[i] <= x && dist2[i] <= y ) { ans = ans > dist1[i] + dist2[i] ? dist1[i] + dist2[i] : ans; } } if (ans == INF) cout << -1 << '\n'; else cout << ans << '\n'; return 0; }