[백준] 1238 파티

백준 1238 파티 문제 풀이입니다.

파티

이 문제는 일반적인 bfs로 풀면 시간초과가 나올만한 노드와 경로 갯수를 가지고 있습니다. 따라서 다익스트라로 접근해야 한다는 것을 알 수 있었습니다.

단방향 그래프이기 때문에 입력받은 순서대로 경로를 만들어주었습니다.

제가 이 문제를 처음에 풀다가 간과한 사실이 하나 있었습니다. 그냥 X번 마을까지 가는 최단거리라 생각했는데 문제를 자세히 보면 오고 가는거리 즉 왕복이 최단으로 되야 했던 것이였습니다.

따라서 우선 모든 학생이 X번 마을까지 도착하는 최단 거리를 다익스트라로 구한 다음에 다시 원래 마을로 돌아가는 다익스트라를 한번 더 돌려서 가장 많은 시간을 소비한 학생을 찾았습니다.

소스코드는 다음과 같습니다.

Source Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define MAX 1001
#define INF 987654321
typedef pair<int, int> p;

int N, M, X;

int result = 0;

vector<p> Road[MAX];
int Dist[MAX];
int Destination_Dist[MAX];

void solve(int start) {
	priority_queue<p, vector<p>, greater<p>> pq; // cost,start

	fill(Dist, Dist + MAX, INF);

	pq.push({ 0,start });
	Dist[start] = 0;

	while (!pq.empty()) {
		int cost = pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		for (auto i : Road[cur]) {
			int next = i.first;
			int next_cost = i.second;

			if (Dist[next] > Dist[cur] + next_cost) {
				pq.push({ Dist[cur] + next_cost,next });
				Dist[next] = Dist[cur] + next_cost;
			}
		}
	}

	result = max(result, Dist[X] + Destination_Dist[start]);

}

int main() {

	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int s, d, t;
		cin >> s >> d >> t;
		Road[s].push_back({ d,t });
	}

	priority_queue<p, vector<p>, greater<p>> pq; // cost,start
	fill(Destination_Dist, Destination_Dist + MAX, INF);

	pq.push({ 0,X });
	Destination_Dist[X] = 0;

	while (!pq.empty()) {
		int cost = pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		for (auto i : Road[cur]) {
			int next = i.first;
			int next_cost = i.second;

			if (Destination_Dist[next] > Destination_Dist[cur] + next_cost) {
				pq.push({ Destination_Dist[cur] + next_cost,next });
				Destination_Dist[next] = Destination_Dist[cur] + next_cost;
			}
		}
	}


	for (int i = 1; i <= N; i++) {
		if (i == X) continue;
		solve(i);
	}

	cout << result;

	system("pause");
	return 0;
}

궁금하신 점은 댓글 남겨 주세요!!

Summary

• 되도록이면 푼 문제들 계속 올리도록 하겠습니다…
• 또 간혹 설명이 이해가 안간다면 말해주시면 그림까지 같이 넣는 노력을 하겠습니다. 감사합니다.