백준 23801 - 두 단계 최단 경로 2(C++)

문제 링크입니다. https://www.acmicpc.net/problem/23801

23801번: 두 단계 최단 경로 2

다익스트라를 사용하는 문제입니다.

무조건 들려야하는 점이 존재할 때,
해당 점을 하나라도 들리면서 갈 수 있는 최소 비용 경로를 구하는 문제입니다.

들려야하는 점의 갯수가 최대 N-3개이니 100,000개 정도가 주어집니다.
따라서, X->K + K->Z를 점마다 확인하는 것은 시간 초과가 될 것입니다.(K를 들려야 하는 점으로 가정)

그렇다면, X->K + K->Z와 같은 방식으로 비용을 구해서 비교해야 하는 것은 맞는데, 어떻게 확인할 수 있을까 생각을 해보면,
시작점은 X에서 들려야 하는 점들까지를 다익스트라로 한번에 구한 뒤, 이를 저장해주고
도착점인 Z에서 들려야 하는 점들까지를 다익스트라로 한번에 구한 뒤, 이전 값에 더해주면,

2번의 다익스트라로 이를 전부 구할 수 있는 방법이 생깁니다.

해당 방법으로 풀면 쉽게 풀 수 있습니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#define INF 9876543210000
#define LL long long
#define F first
#define S second

using namespace std;

int N, M, P;
int X, Z;
int Point[100001];
LL Distance[100001];
LL Point_distance[100001]; // 들려할 지점을 들리면서 가는데 필요한 최소 비용
vector<pair<int, int>> connect[100001];
priority_queue<pair<LL, int>, vector<pair<LL, int>>> q;

void reset_distance(){
	for(int i = 1; i <= N; i++) Distance[i] = INF;
}

void Dijstra(int st){
	reset_distance();
	Distance[st] = 0;
	q.push({-Distance[st], st});
	while(!q.empty()){
		int x = q.top().S;
		LL cost = -q.top().F;
		q.pop();
		if(Distance[x] < cost) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			LL n_cost = cost + connect[x][i].S;
			if(Distance[xx] > n_cost){
				Distance[xx] = n_cost;
				q.push({-Distance[xx], xx});
			}
		}
	}
}

void solve(){
	LL min_cost = INF;
	Dijstra(X); //X에서 들려할 지점까지 최소 거리
	for(int i = 1; i <= P; i++){
		Point_distance[i] += Distance[Point[i]];
	}
	Dijstra(Z); //Z에서 들려할 지점까지 최소 거리
	for(int i = 1; i <= P; i++){
		Point_distance[i] += Distance[Point[i]];
	}
   // 위에서 구한 두 최소거리를 더함으로 두번의 다익스트라로 모든 경우를 확인 가능하다.
   // 시작점에서 -> K + K -> 도착점을 더함으로써 이동간의 최소거리를 알 수 있다.
	for(int i = 1; i <= P; i++){
		if(min_cost > Point_distance[i]){
			min_cost = Point_distance[i];
		}
	}
	if(min_cost == INF) cout << "-1";
	else cout << min_cost;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		scanf("%d %d %d", &x, &y, &cost); //시간을 아끼기 위함
		connect[x].push_back({y, cost});
		connect[y].push_back({x, cost});
	}
	cin >> X >> Z;
	cin >> P;
	for(int i = 1; i <= P; i++) scanf("%d", &Point[i]);
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.