(BOJ) 13911 집 구하기

문제: https://www.acmicpc.net/problem/13911

 

문제 풀이:

맥도날드가 있는 곳, 스타벅스가 있는 곳에서 각각 시작해서 다익스트라 돌림

각 정점을 입력 받을 때 pq에 (0,시작정점)으로 넣어넣고 시작하면 한번에 돌릴 수 있음

 

 

소스 코드:

typedef pair<int, int> P;
int n, m, macs, stars, x, y, dist[2][10001],res=inf;
bool visit[2][10001];
vector<vector<P>> adj;
typedef priority_queue<P, vector<P>, greater<P>> Prior;
Prior tmp,tmp2;
void di(int cnt,Prior pq) {
	
	while (!pq.empty()) {
		int cur;
		do {
			cur = pq.top().second;
			pq.pop();
		} while (!pq.empty() && visit[cnt][cur]);

		if (visit[cnt][cur]) break;
		visit[cnt][cur] = true;

		for (auto& next : adj[cur]) {
			if (dist[cnt][next.second] > dist[cnt][cur] + next.first) {
				dist[cnt][next.second] = dist[cnt][cur] + next.first;
				pq.push({ dist[cnt][next.second] ,next.second });
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m;
	fill(dist[0], dist[0] + n + 1, inf);
	fill(dist[1], dist[1] + n + 1, inf);

	adj.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int q, w, e;
		cin >> q >> w >> e;
		adj[q].push_back({ e,w });
		adj[w].push_back({ e,q });
	}
	cin >> macs >> x;
	for (int i = 0; i < macs; i++) {
		int q;
		cin >> q;
		tmp.push({ 0,q });
		dist[0][q] = 0;
	}
	cin >> stars >> y;
	for (int i = 0; i < stars; i++) {
		int q;
		cin >> q;
		tmp2.push({ 0,q });
		dist[1][q] = 0;
	}
	di(0,tmp);
	di(1, tmp2);
	int t = inf;
	for (int i = 1; i <= n; i++) {
		if (dist[0][i] != 0 && dist[0][i]<=x&& dist[1][i] != 0 && dist[1][i] <= y) {
			res = min(res, dist[0][i] + dist[1][i]);
		}
	}
	
	if (res == inf) cout << "-1\n";
	else cout << res << '\n';
	return 0;
}