BOJ 1238 - 파티

문제

\(N\)개의 정점에 대한 \(M\)개의 단방향 간선이 주어진다.
이때 모든 정점에 대해서, 한 정점 \(X\)로 향하는 최단 경로, \(X\)에서부터 도착하는 최단 경로의 합의 최댓값을 구하는 문제이다.

\(1\le N \le 1000,\; 1\le M \le 10000,\; 1\le X \le N\)이다.
간선의 가중치 \(T_i\)에 대해 \(1 \le T_i \le 100\)이다.

풀이

단순히 다익스트라를 N+1번 돌려서 풀 수도 있다.
다익스트라가 1 to n 최단 경로를 구하는 알고리즘이기 때문에, 각 정점에서 출발하는 것 N번 수행, X에서 출발하는 것 1번 수행하여 모든 정점에서의 오고 가는 시간을 구할 수 있다.

그래프가 단방향 그래프이기 때문에, 간선들의 방향을 바꾸고 X에서 출발하는 최소 경로들을 구하면 각 도착점들에서 출발하는 최소 경로를 구하는 것과 같다.
따라서 간선 방향을 바꾸기 전 후로 X에서 출발하는 최소 경로를 구하면 위와 같은 결과를 얻을 수 있다.

소스코드

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

using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using lld = long long;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, x, ans = 0;
	cin >> n >> m >> x;
	x--;
	vi ttime(n, 0);
	vector<vi> adj(n, vi(0));
	for (int i = 0; i < m; i++)
	{
		int w, s, e;
		cin >> s >> e >> w;
		s--, e--;
		adj[s].push_back(e * 1000 + w);
	}
	vi vis(n, 1000001);
	queue<int> q;
	q.push(x);
	vis[x] = 0;
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (int i = 0; i < adj[cur].size(); i++)
		{
			int adjv = adj[cur][i] / 1000, w = adj[cur][i] % 1000;
			if (vis[adjv] >= vis[cur] + w)
			{
				vis[adjv] = vis[cur] + w;
				q.push(adjv);
			}
		}
	}
	for (int i = 0; i < n; i++)
		ttime[i] += vis[i];

	vector<vi> radj(n, vi(0));
	vis = vi(n, 1000001);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < adj[i].size(); j++)
			radj[adj[i][j] / 1000].push_back(i * 1000 + adj[i][j] % 1000);
	q.push(x);
	vis[x] = 0;
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (int i = 0; i < radj[cur].size(); i++)
		{
			int adjv = radj[cur][i] / 1000, w = radj[cur][i] % 1000;
			if (vis[adjv] >= vis[cur] + w)
			{
				vis[adjv] = vis[cur] + w;
				q.push(adjv);
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		ttime[i] += vis[i];
		if (ans < ttime[i])
			ans = ttime[i];
	}
	cout << ans;
	return 0;
}

풀고나서

• 처음에는 플로이드 워셜을 떠올렸지만, 구현 방법이 생각나지 않아 다익스트라로 풀었다.