백준 2398 - 3인통화(C++)

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

2398번: 3인통화

다익스트라와 백트래킹을 이용한 문제였습니다.

3자 통화를 할 때 드는 최소 비용과 이때의 연결된 링크의 갯수, 어떤 링크인지를 출력하는 문제입니다.

먼저 3자 통화를 하는데 필요한 최소 비용을 구하는 것부터 해보겠습니다.
N개의 정점에서 세명의 위치까지의 최소거리를 구한 후 값을 더해 각 정점에서 출발했을 때의 값을 각각 구한다면
N(<=1000)개의 다익스트라 탐색을 해야합니다.
따라서, 다른 방법인 세사람을 시작점으로 설정한 뒤, 각 위치에서 다른 정점까지의 거리를 구할 것입니다.
그런 후, 세 사람이 X번 정점까지의 최소거리를 구한다면 3번의 다익스트라 탐색으로 최소 거리를 구할 수 있습니다.

이번에는 링크의 갯수와 연결된 링크입니다.
연결된 링크를 구한다면 링크의 갯수도 알 수 있기에 한번에 구할 수 있습니다.
다익스트라 탐색 중, queue에 새로운 값을 넣는다면 이는 지금까지의 최소 거리라고 생각할 수 있습니다.
따라서, 이때 배열을 하나 이용해 parent[다음 정점] = 현재 정점 으로 해주면 부모를 쉽게 저장할 수 있습니다.
탐색이 전부 끝난 뒤, 마지막 정점에서 시작 정점으로 거슬러 가면서 이어진 링크를 찾아주면 됩니다.


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

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF INT_MAX
#define F first
#define S second

using namespace std;
int N, M;
vector<pair<int, int>> connect[1001];
vector<pair<int, int>> line; // 어떤 링크를 사용했는지
int Distance[3][1001]; // 3개의 출발점에서의 각 정점들까지 최소거리
int parent[3][1001]; // 3개의 츨발점에서의 각 정점들의 부모
int start[3];
priority_queue<pair<int, int>> q;

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

void Dijstra(int st){
	parent[st][start[st]] = start[st];
	Distance[st][start[st]] = 0;
	q.push({-0, start[st]});
	while(!q.empty()){
		int x = q.top().S;
		int cost = -q.top().F;
		q.pop();
		if(Distance[st][x] < cost) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			int n_cost = cost + connect[x][i].S;
			if(Distance[st][xx] > n_cost){
				parent[st][xx] = x; // 다음 정점의 부모는 현재 정점
				Distance[st][xx] = n_cost;
				q.push({-Distance[st][xx], xx});
			}
		}
	}
}

void solve(){
	int point = 0, cost = INF;
	reset_distance();
	for(int i = 0; i < 3; i++){
		Dijstra(i);
	}
	for(int i = 1; i <= N; i++){
		if(Distance[0][i] == INF || Distance[1][i] == INF || Distance[2][i] == INF) continue;
		if(cost > Distance[0][i] + Distance[1][i] + Distance[2][i]){
			cost = Distance[0][i] + Distance[1][i] + Distance[2][i];
			point = i;
		}
	}
	for(int i = 0; i < 3; i++){
		for(int j = point; j != start[i]; j = parent[i][j]){ // 연결된 정점 확인
			line.push_back({min(j, parent[i][j]), max(j, parent[i][j])});
		}
	}
	cout << cost << " " << line.size() << "\n";
	for(int i = 0; i < line.size(); i++){
		cout << line[i].F << " " << line[i].S << "\n";
	}
}

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});
	}
	for(int i = 0; i < 3; i++) cin >> start[i];
	solve();
	return 0;
}

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