백준 1238 - 파티(C++)

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

1238번: 파티

다익스트라 알고리즘을 사용해 푸는 문제입니다.

K번 학생이 X번 정점을 왕복할 때의 최단 시간을 구하는 문제입니다.

1 ~ N번 학생의 최단 시간 중에서 최댓값을 구하면 됩니다.

 

이때 주어진 간선은 단방향이니, 한쪽 방향으로만 저장해야 합니다.

왕복 값을 구해야하지만, 1 ~ N번점부터 X번 점까지 각각 값을 구하기에는 복잡해집니다.

따라서 X번 점에서 1 ~ N번 점까지의 최소 거리를 2번 구함으로서 왕복 거리를 구할 것입니다.

 

해당 설명을 참고해주세요.

그래프를 정방향으로, 반대 방향으로 저장한 뒤, 각각 다익스트라를 통해서 돌아올 때, 갈 때의 거리 값을 구할 수 있습니다. 이 두 그래프에서의 값을 더한다면, 해당 점에서의 왕복 값임을 알 수 있습니다.

따라서 왕복 값을 구했으니, 왕복 값의 최댓값을 구하면 됩니다.

 

이 방법의 장점은 두 그래프 전부 X점에서 시작해도 되는 것입니다.

 

 

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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#define INF 210000000000

using namespace std;

priority_queue < pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
long long Distance_go[1001];
long long Distance_back[1001];
int N, M, X;
vector<pair<int, int>> line_go[1001];
vector<pair<int, int>> line_back[1001];

void Dijkstra_go(int start) {
	for (int i = 1; i <= N; i++) Distance_go[i] = INF;
	Distance_go[start] = 0;
	q.push({ 0, start });
	while (!q.empty()) {
		int x = q.top().second;
		long long cost = q.top().first;
		q.pop();
		for (int i = 0; i < line_go[x].size(); i++) {
			int xx = line_go[x][i].first;
			int Cost = line_go[x][i].second;
			if (Distance_go[xx] > Distance_go[x] + Cost) {
				Distance_go[xx] = Distance_go[x] + Cost;
				q.push({ Distance_go[xx] , xx });
			}
		}
	}
}

void Dijkstra_back(int start) {
	for (int i = 1; i <= N; i++) Distance_back[i] = INF;
	Distance_back[start] = 0;
	q.push({ 0, start });
	while (!q.empty()) {
		int x = q.top().second;
		long long cost = q.top().first;
		q.pop();
		for (int i = 0; i < line_back[x].size(); i++) {
			int xx = line_back[x][i].first;
			int Cost = line_back[x][i].second;
			if (Distance_back[xx] > Distance_back[x] + Cost) {
				Distance_back[xx] = Distance_back[x] + Cost;
				q.push({ Distance_back[xx] , xx });
			}
		}
	}
}

void solve() {
	long long ans = 0;
	Dijkstra_go(X);
	Dijkstra_back(X);
	for (int i = 1; i <= N; i++) {
		ans = max(ans, Distance_go[i] + Distance_back[i]);
	}
	cout << ans;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> X;
	for (int i = 1; i <= M; i++) {
		int x, y, cost;
		cin >> x >> y >> cost;
		line_go[y].push_back({ x, cost });
		line_back[x].push_back({ y,cost });
	}
	solve();
	return 0;
}

 

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