백준 23793 - 두 단계 최단 경로 1(C++)

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

23793번: 두 단계 최단 경로 1

다익스트라를 이용한 문제입니다.

문제 시간이 0.3초이며, N과 M의 값이 큰 만큼, 시간을 생각하면서 풀어야하는 문제입니다.

먼저, 문제를 풀기 위해 방향을 생각해보겠습니다.
두개를 출력하면 됩니다.
1. X -> Y -> Z를 들려서 올 때의 최소 비용
2. X -> Z(Y를 제외)로 올 때의 최소 비용

2번은 간단합니다. 다익스트라를 실행할 때, Y점에 도달한다면, 해당 경우를 건너뛰기만 하면 됩니다.

1번의 경우, X -> Z로 시작점과 끝점을 정해 돌린다면, 해당 경우의 최소비용이 Y점을 지난다는 확신이 없습니다.
이럴 경우, X -> Y의 최소 비용과 Y -> Z의 최소 비용을 각각 구해 더해주면 됩니다.

여기서 시간을 줄이기 위해서 생각해봐야하는 것은
많은 경우가 같은 정점, 다른 비용으로 큐에 넣어질 것입니다.
같은 정점, 다른 비용을 모두 확인하는 것과, 같은 정점, 최소 비용인 하나만 확인하는 것과 결과는 같지만 시간은 다릅니다.
따라서, K라는 정점을 도착했을 때, 이전에 저장되어있는 최소 비용과 비교해, 크다면 해당 경우를 확인할 필요가 없어집니다.


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

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#define INF 210000000000
#define LL long long // 값이 int 범위를 넘어설 수 있으므로 long long을 사용한다.
#define F first
#define S second

using namespace std;

int N, M;
int X, Y, Z;
vector<pair<int, LL>> connect[100001];
LL Distance[100001];
priority_queue<pair<LL, int>, vector<pair<LL, int>>> q;

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

LL Dijstra(int st, int fin, int way){ // way가 1일 경우 Y 패싱
	reset_distance();
	Distance[st] = 0;
	q.push({-0, 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 = connect[x][i].S + cost;
			if(way == 1 && xx == Y) continue; // way가 1일 때는 Y값을 빼고 지나친다.
			if(Distance[xx] > n_cost){
				Distance[xx] = n_cost;
				q.push({-Distance[xx], xx});
			}
		}
	}
	return Distance[fin];
}

void solve(){
	LL method_1 = Dijstra(X, Y, 0) + Dijstra(Y, Z, 0); // Y를 포함하고 달렸을 떄
	LL method_2 = Dijstra(X, Z, 1); // Y를 뺴고 달렸을 때
	if(method_1 >= INF) method_1 = -1;
	if(method_2 >= INF) method_2 = -1;
	cout << method_1 << " " << method_2;

}

int main() {
	cin.tie(0);
	cout.tie(0);
	scanf("%d %d", &N, &M);
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		scanf("%d %d %d", &x, &y, &cost); // 시간초과를 대비해 scanf를 사용
      connect[x].push_back({y, cost});
	}
	cin >> X >> Y >> Z;	
	solve();
	return 0;
}

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