백준 1238 파티

https://www.acmicpc.net/problem/1238

1238번: 파티

 

다익스트라 알고리즘이랑 메모이제이션을 섞어서 풀었다.

 

이중 배열을 이용한 다익스트라 알고리즘은 시간복잡도가 O(N^2)인데 반해서 

 

우선순위 큐를 이용하면 O(N * log N)까지 줄일 수 있다.

 

1. 각 점에서 X까지 최단거리를 다익스트라를 이용해서 구한다. 이 때 지나치는 정점을 활용하는 게 중요하다

 

예를 들어서 1 -- > 2 --> 3 --> X가 경로라면 2 --> X의 비용은 1 --> X에서 1 --> 2를 뺀 값이다. 

 

이를 활용하면 불필요한 반복을 피할 수 있다.

 

2. X에서 각 점까지 최단거리를 다익스트라를 이용해서 구한다. 

 

3. 1과 2를 더해서 제일 비용이 큰 애를 구한다. 

 

/* 파티 */

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define pp pair<int,int>
#define MAX 1000+1

using namespace std;

int n_of_student, n_of_road, target_student;
int x_to_student[MAX], student_to_x[MAX];
vector<int> dist;
bool is_visit[MAX];

vector<pp> edge[1000 + 1];

void input();
void solve();

int bfs(int st, int);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	input();
	solve();

	return 0;
}

void input() {
	cin >> n_of_student >> n_of_road >> target_student;
	for (int i = 0; i < n_of_road; i++) {
		int source_student, target_student, cost;
		cin >> source_student >> target_student >> cost;
		edge[source_student].push_back({ target_student, cost }); // 간선 정보 저장하기
	}
}

int bfs(int st, int tt) {
	priority_queue<pp> pq; // 우선순위 Queue를 활용한 다익스트라는 무려 O(N * LogN)
	pq.push({ 0, st });
	fill(dist.begin(), dist.end(), 987654321);

	dist[st] = 0;
	while (!pq.empty()) {

		int current_node_number = pq.top().second;
		int current_node_distance = -1 * pq.top().first; // 가까운 순서대로 처리하거라
		pq.pop();
		if (current_node_number == tt) {
			return current_node_distance;
		}

		// 현재 최적거리보다 더 멀면 점검할 필요 없다.
		if (dist[current_node_number] < current_node_distance) continue;

		for (int i = 0; i < edge[current_node_number].size(); i++) {
			int next_node_distance = current_node_distance + edge[current_node_number][i].second;
			int next_node = edge[current_node_number][i].first;

			if (dist[next_node] > next_node_distance) {
				dist[next_node] = next_node_distance;
				pq.push({ -1 * next_node_distance, next_node });
			}
		}
	}
}

void solve() {

	dist.resize(n_of_student + 1);
	for (int i = 1; i <= n_of_student; i++) {
		if (i == target_student) continue;
		x_to_student[i] = bfs(target_student, i);  
		student_to_x[i] = bfs(i, target_student);
	}	
------------------------ O(N * N * LogN) ---------------- 
	for (int i = 1; i <= n_of_student; i++) {
		x_to_student[i] += student_to_x[i];
	}
-----------------------O (N) 이니까 아직 O(N * N * LogN) ---------------

	sort(x_to_student, x_to_student + n_of_student + 1);
    ----------------------- O(N * Log N)이니까 아직 O(N * N * LogN) -----------
    끝!
	cout << x_to_student[n_of_student] << '\n';

}