[BOJ 23258 // C++] 밤편지

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 23258번 문제인 밤편지이다.
문제는 아래 링크를 확인하자.

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

23258번: 밤편지

먼저 각 반딧불은 상수 C에 따라 집의 번호가 C 미만인 집들만을 방문할 수 있게 된다. 이들 집의 모든 이슬을 마시더라도 2^C보다 적은 이슬을 마시게 되므로 방문할 수 있는 집의 개수 제한은 없다.

 

주어진 쿼리들을 C가 작은 쿼리부터 하나씩 보면서 Floyd-Warshall 알고리즘을 (이전 상태에서부터 이어서) C 미만의 노드까지만 진행시켜 집의 번호가 C 이상인 집들을 중간에 거치는 경우가 없는 최단거리를 구하고, 쿼리의 입력순으로 답을 출력해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

struct query {
	int s, e, C, idx;
	query() {};
	query(int s, int e, int C, int idx) {
		this->s = s, this->e = e, this->C = C, this->idx = idx;
	}
};

bool comp(query q1, query q2) {
	return q1.C < q2.C;
}

ll dist[301][301];
int ans[500000];
query queries[500000];

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


	int N, Q; cin >> N >> Q;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			cin >> dist[r][c];
			if (r != c && dist[r][c] == 0) dist[r][c] = 1000000007;
		}
	}

	for (int q = 0; q < Q; q++) {
		int C, s, e; cin >> C >> s >> e;
		queries[q] = query(s, e, C, q);
	}

	sort(queries, queries + Q, comp);

	int k = 1;
	for (int q = 0; q < Q; q++) {
		auto& qry = queries[q];
		int C = qry.C;
		while (k < C) {
			for (int r = 1; r <= N; r++) {
				for (int c = r + 1; c <= N; c++) {
					if (dist[r][k] + dist[k][c] < dist[r][c]) dist[r][c] = dist[c][r] = dist[r][k] + dist[k][c];
				}
			}
			k++;
		}
		if (dist[qry.s][qry.e] > 1000000000) ans[qry.idx] = -1;
		else ans[qry.idx] = dist[qry.s][qry.e];
	}

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