Boj 1602) 도망자 원숭이

문제

백준 1602

어떤 경로의 시간는 그것을 이루는 간선의 가중치들과 정점의 최대 가중치를 더한 값으로 문제에서 정의된다.

우리는 경로를 모르므로 최대 가중치를 고정시키자. 시작점을 a, 끝점을 b, 최대 가중치를 가진 정점을 p 라고 하면 최단시간은 다음과 같다.

1. a->p 의 최단경로 + p->b 의 최단경로 + p 의 가중치
2. 이때의 최단경로는 p 의 가중치보다 작은 정점으로만 이루어져야한다.

주어진 쿼리의 특성 상 우리는 임의의 두 점 사이의 최단경로가 필요하다. 이를 위해 잘 알려진 두가지 방법으로 Floyd Warshall 과 Dijkstra 이 있고 두 방법으로 모두 풀 수 있다. 이때 2번 성질을 만족시키기 위해 약간의 트릭이 추가된다.

나는 처음에 Floyd Warshall 로 풀었고 후자의 방법은 답지를 봤는데 후자가 더 좋은방법 같다. 이 문제는 간선이 작아 속도도 더 빠르고 구현도 간단하기 때문이다.

Floyd Warshall

Floyd Warshall 의 가장 바깥 루프를 돌 때의 성질이 있다. 루프마다 시작점과 끝점 사이에 경유할 수 있는 정점이 추가된다는 것이다.

이 성질을 이용해서 중간경로가 되는 정점을 작은 가중치를 가진 정점 순서로 추가한다. 그러면 2번 성질을 만족하는 최단경로를 구할 수 있다.

시간 복잡도

O(\(N^3 + NQ\))

코드

const int MAX_IN = 501;
int edges[MAX_IN][MAX_IN];
int nodes[MAX_IN];
int ranks[MAX_IN];

int main()
{
	fill(edges[0], edges[MAX_IN], 1e9);
	for (int i = 1; i <= MAX_IN; i++) edges[i][i] = 0;

	int n, m, q;
	cin >> n >> m >> q;

	for (int i = 1; i <= n; i++) cin >> nodes[i];
	for (int i = 0; i < n; i++) ranks[i] = i+1;
	sort(ranks, ranks + n, [](int a, int b) { return nodes[a] < nodes[b]; });

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edges[a][b] = edges[b][a] = c;
	}

	vector<pair<int,int>> queries;
	for(int i = 0; i < q; i++)
	{
		int s, e; cin >> s >> e;
		queries.emplace_back(s, e);
	}

	vector<int> ans(q, 1e9);
	for (int k = 0; k < n; k++)
	{
		int mid = ranks[k];

		for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
			if (edges[i][j] > edges[i][mid] + edges[mid][j])
				edges[i][j] = edges[i][mid] + edges[mid][j];

		for (int i = 0; i < q; i++)
		{
			int s = queries[i].first, e = queries[i].second;
			if (edges[s][mid] != 1e9 && edges[mid][e] != 1e9)
			{
				int w = max(nodes[mid], max(nodes[s], nodes[e]));
				ans[i] = min(ans[i], edges[s][mid] + edges[mid][e] + w);
			}
		}
	}

	for(auto an : ans) cout << (an == 1e9 ? -1 : an) << '\n';
}

Dijkstra

최대가중치를 가질 임의의 정점으로부터의 최단경로를 구하는 것은 Dijkstra 를 \(N\) 번 돌려서 해결할 수 있다.

이때 시작점보다 가중치가 같거나 작은 정점만 지나야 하는데 조건문에 조건을 하나 더 추가하면 간단히 처리할 수 있다.

시간 복잡도

O(\(NE\log{E} + NQ\))

• 주어진 조건에서 \(E\) 의 크기가 작아서 플로이드보다 더 빠르다.

코드

struct E { int d, w; };
namespace std {
	template<> struct greater<E> {
		bool operator()(const E& a, const E& b) const { return a.w > b.w; }
	};
}

const int MAX_IN = 501;
vector<E> edges[MAX_IN];
int dp[MAX_IN][MAX_IN];
int nodes[MAX_IN];
int n; // vertex number

void Dijkstra(int start, int* dp)
{
	fill(dp, dp + n + 1, 1e9);
	priority_queue<E, vector<E>, greater<E>> q;
	dp[start] = 0; q.push({ start, 0 });

	while (!q.empty())
	{
		E cur = q.top(); q.pop();
		if (dp[cur.d] < cur.w) continue;
		for (E& l : edges[cur.d])
			if (dp[cur.d] + l.w < dp[l.d] && 
				nodes[start] >= nodes[l.d]) // equal 조건 필요함에 주의
			{
				dp[l.d] = dp[cur.d] + l.w;
				q.push({ l.d, dp[l.d] });
			}
	}
}

int main()
{
	int m, q;
	cin >> n >> m >> q;

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

	for (int i = 1; i <= n; i++) Dijkstra(i, dp[i]);

	for(int i = 0; i < q; i++)
	{
		int s, e, ans = 1e9; cin >> s >> e;
		for (int mid = 1; mid <= n; mid++)
			ans = min(ans, dp[mid][s] + dp[mid][e] + nodes[mid]);
		cout << (ans == 1e9 ? -1 : ans) << '\n';
	}
}