백준 - 1238(파티) - C++

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

문제설명

• 문제는 간단하게 단방향 간선의 정보가 주어질 때 모든 노드에서 특정 노드 x로의 왕복 비용의 최대값을 return 해주는 문제이다.

접근 방법

• N이 최대 1000이고, M이 최대 10000이다. 따라서 우선순위 큐를 사용하면 O(MlogN)의 시간 복잡도를 갖는데, 여기서 모든 노드에 대해 탐색하므로,O(NMlogN)의 시간 복잡도를 갖게 된다. 이는 제한시간 1초 이내로 가능하다.
• 플로이드 와샬로 접근을 한다면 N의 최대 1000에 대해 O(N^3)의 시간복잡도로 1억번의 연산이 예상된다. 이는 C++로 한다면 아슬아슬하게 가능하지만, 다른언어는 힘들 것으로 생각한다.

풀이

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std; 
vector<pair<int,int>> v[1001];
int ans[1001][1001];
void dij(int start) {
	// min heap형태의 priority_queue 선언
	// cost, next node 형태로 저장 -> first를 기준으로 정렬되기 때문에
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	ans[start][start] = 0;
	pq.push({ 0,start });
	while (!pq.empty()) {
		int cur = pq.top().second;
		int cost = pq.top().first;
		pq.pop();
		if (ans[start][cur] < cost) continue;
		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i].first;
			int nextcost = cost + v[cur][i].second;
			if (nextcost < ans[start][next]) {
				ans[start][next] = nextcost;
				pq.push({ nextcost ,next });
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, x;
	cin >> n >> m >> x;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ans[i][j] = 999999999;
		}
	}
	int a, b, c;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
	}
	
	for (int i = 1; i <= n; i++) {
		dij(i);
	}

	int MAX = -1;
	for (int i = 1; i <= n; i++) {
		if (MAX < ans[i][x] + ans[x][i]) MAX = ans[i][x] + ans[x][i];
	}
	cout << MAX;
	return 0;
}

결과