BOJ 1238 파티

www.acmicpc.net/problem/1238

1238번: 파티

 

다익스트라 응용문제로, 단방향 그래프의 방향을 바꿔서 다익스트라를 돌리면

모든 정점에서 한 정점으로 가는 거리를 구할 수 있다.

 

따라서 파티장 x가 주어지면

a에서 b로 가는 그래프 외에

b에서 a로 가는 그래프도 입력을 받아주고

각각에 대해서 다익스트라를 사용한 뒤에 두 배열의 합 중에서 가장 큰 값이 정답이 된다.

 

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

const int INF = 1e9;
priority_queue<pair<int, int>> pq;
vector<pair<int, int>> ar[1001], ar2[1001];
int n, m, x, a, b, c;

vector<int> dijkstra(int s, vector<pair<int, int>> ar[]) {
	vector<int> d(n, INF);
	d[s] = 0;
	pq.push({ 0,s });

	while (!pq.empty()) {
		int cur = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if (d[cur] < cost) continue;
		for (auto i : ar[cur]) {
			int nc = cost + i.second;
			if (nc < d[i.first]) {
				d[i.first] = nc;
				pq.push({ -nc,i.first });
			}
		}
	}

	return d;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m >> x;
	for (int i = 0; i < m; ++i) {
		cin >> a >> b >> c;
		ar[b - 1].push_back({ a - 1,c });
		ar2[a - 1].push_back({ b - 1,c });
	}

	vector<int> back = dijkstra(x - 1, ar);
	vector<int> go = dijkstra(x - 1, ar2);
	vector<int> ans;

	for (int i = 0; i < n; ++i) {
		//cout << back[i] << ' ' << go[i] << '\n';
		ans.push_back(back[i] + go[i]);
	}

	cout << *max_element(ans.begin(), ans.end()) << endl;

	return 0;
}

 

방향이 바뀔 경우 모든 정점에서 한 정점으로 가는 거리가 나온다는 특성을 알고 있었다면

쉽게 풀리는 문제였다.