[BOJ] 1238 파티

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

1238번: 파티

다익스트라 문제..

이 문제를 이전에는 인접 행렬로 풀었었는데

N = 1000이기 때문에 인접 행렬은 총 1,000,000개의 int 변수가 필요하다.

하지만 총 간선의 개수가 10000개 이하로 정해져있기 때문에

인접 행렬보다는 인접 리스트가 메모리상 효율적이고 시간복잡도 상에서도 더욱 효율적이다.

좀 더 최적화적인 관점에서 문제를 바라볼 필요가 있겠다.

그리고, C++은 기본적으로 우선순위 큐가 최대힙으로 구현되어 있기 때문에

최소 힙을 위해선 그냥 간단하게 부호를 바꿔서 넣어주면 되겠다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;
int N, M, X, from, to, T;
vector<pair<int, int>> adjList[1001];
vector<pair<int, int>> radjList[1001];
bool visited[1001];
int dist[1001];
int result[1001];
priority_queue<pair<int, int>> pq;

void go(int X, vector<pair<int, int>> adjList[1001]) {
	//pq 초기화
	while (!pq.empty()) pq.pop();
	for (int i = 1; i <= N; i++) {
		visited[i] = false; dist[i] = 0x7fffffff;
	}

	//pq에 시작점 넣고, 방문처리
	dist[X] = 0;
	pq.push({ -dist[X], X});

	while (!pq.empty()) {
		int c = pq.top().second;
		int t = -pq.top().first;
		pq.pop();
		if (visited[c]) continue;

		visited[c] = true;
		result[c] += t;

		for (int i = 0; i < adjList[c].size(); i++) {
			int n = adjList[c][i].first;
			int cost = adjList[c][i].second;
			if (!visited[n] && dist[n] > dist[c] + cost) {
				dist[n] = dist[c] + cost;
				pq.push({ -(dist[c] + cost), n });
			}
		}
		
	}
}

void solution() {
	go(X, adjList);
	go(X, radjList);
}

void input() {
	cin >> N >> M >> X;
	for (int i = 0; i < M; i++) {
		cin >> from >> to >> T;
		adjList[from].push_back({ to, T });
		radjList[to].push_back({ from, T });
	}
}

void output() {
	int answer = 0;
	for (int i = 1; i <= N; i++) {
		answer = max(result[i], answer);
	}

	cout << answer << "\n";
}

int main() {
	input();
	solution();
	output();
}