Boj 25500) 무자비한 최소경로

문제

백준 25500

설명

행성터널 + 환승

간선이 \(\mathrm{N}^2\) 로 존재하므로 이를 줄이는 것이 관건인 문제이다.

X, Y 좌표의 경우 행성터널 문제처럼 축에 대해 정렬 후 인접정점을 잇는 Greedy 전략을 사용하면 된다. 증명도 어렵지 않다.

Z 좌표의 경우 여러 정점이 K 의 모듈러에 의해 복잡하게 연결되어 있다. 이는 환승 문제처럼 정점들을 공통적으로 묶는 정점을 추가해 간선을 선형 단위로 줄일 수 있다.

이 두가지 테크닉만 알고 있었으면 간단하게 해결했을 문제.

참고로 int 에서는 오버플로우가 나므로 64bit 자료형을 사용해야한다.

시간 복잡도

O(\(\mathrm{N}\log{ \mathrm{N}}\))

코드

const int MAX_IN = 200002;

struct E { int d; long long w; };
namespace std {
	template<> struct greater<E> {
		bool operator()(const E& a, const E& b) const { return a.w > b.w; }
	};
}
vector<E> lines[2*MAX_IN];
long long dp[2*MAX_IN];
int n, k; // vertex number

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

	while (!q.empty())
	{
		E cur = q.top(); q.pop();
		if (dp[cur.d] < cur.w) continue;  // out of updated edge

		for (E& l : lines[cur.d])
		{
			if (dp[cur.d] + l.w < dp[l.d])
			{
				dp[l.d] = dp[cur.d] + l.w;
				q.push({ l.d, dp[l.d] });
			}
		}
	}
}

struct V { int x, y; }  arr[MAX_IN];

int main(void)
{
	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		int z, kz;
		cin >> arr[i].x >> arr[i].y >> z;

		// Z 좌표를 정점으로 따로 뺌
		kz = z % k;
		lines[i].push_back({ n + kz, z });
		lines[n + (k - kz)%k].push_back({ i, z });
	}

	vector<int> idx; 
	for (int i = 0; i < n; i++) idx.push_back(i);

	// x 축 정렬 후 인접정점 연결
	sort(idx.begin(), idx.end(), [](int i, int j) { return arr[i].x < arr[j].x; });
	for (int i = 0; i < n - 1; i++) lines[idx[i]].push_back({ idx[i + 1], abs(arr[idx[i]].x - arr[idx[i + 1]].x) });
	for (int i = n - 1; i > 0; i--) lines[idx[i]].push_back({ idx[i - 1], abs(arr[idx[i]].x - arr[idx[i - 1]].x) });

	// z 축 정렬 후 인접정점 연결
	sort(idx.begin(), idx.end(), [](int i, int j) { return arr[i].y < arr[j].y; });
	for (int i = 0; i < n - 1; i++) lines[idx[i]].push_back({ idx[i + 1], abs(arr[idx[i]].y - arr[idx[i + 1]].y) });
	for (int i = n - 1; i > 0; i--) lines[idx[i]].push_back({ idx[i - 1], abs(arr[idx[i]].y - arr[idx[i - 1]].y) });

	Dijkstra(0);

	for (int i = 0; i < n; i++) cout << dp[i] << '\n';
}