[BAE/<JOON> 문제풀이] 2157. 여행

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

2157번: 여행

서론

KCM Travel 열화 버전 문제. 최적이 아닌 탐색도 유지해야한다는 점이 같다.

풀이

KCM 과의 차별점은 정점을 항상 오름차순으로만 방문하도록 제한된다는 점(1) 탐색 줄기 정보 중 하나가 방문 정점 개수이므로 현재 줄기 유지 여부를 상수 시간에 판단 할 수 있다는 점(2)이다.

각각 풀어서 설명하면 다음과 같다.

(1) : 상수 줄이는 거 말고 별 의미는 없다. 

(2) : 방문 정점 개수를 오름차순으로 정렬해 방문할 때 이미 방문한 정점 ( 더 적은 정점을 방문한 탐색 )  보다 점수가 적은 경우 그 탐색은 유지할 필요가 없다. 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct p {
	int s, d, v, cnt;
};
struct cmp {
	bool operator()(p a, p b) {
		return a.cnt > b.cnt;
	}
};
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m, k; cin >> n >> m >> k; vector<vector<p>> pl(n + 1, vector<p>(n + 1)), pd(n + 1); vector<vector<int>> dp(n + 1, vector<int>(m + 1)); vector<int> dp2(n + 1, 2100000000);
	for (int i = 1; i <= k; i++) {
		int s, d, v; cin >> s >> d >> v;
		if (d < s || pl[s][d].v > v) continue;
		pl[s][d] = { s, d, v, 0 };
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (pl[i][j].v > 0) {
				pd[i].push_back({ j, j, pl[i][j].v, 0 });
			}
		}
	}
	pl = pd;
	priority_queue<p, vector<p>, cmp> q;
	q.push({ -1, 1, 0, 1 });
	while (!q.empty()) {
		p cur = q.top(); q.pop();
		for (const auto& nx : pl[cur.d]) {
			if (nx.v > 0 && cur.cnt + 1 <= m && dp[nx.d][cur.cnt + 1] < cur.v + nx.v) { // 나중에 도착한 애가 값까지 작으면 스킵
				dp[nx.d][cur.cnt + 1] = cur.v + nx.v;
				if (nx.d == n) continue;
				q.push({ nx.d, nx.d, cur.v + nx.v, cur.cnt + 1 });
			}
		}
	}
	int mx = -1;
	for (int i = 1; i <= m; i++) {
		mx = mx > dp[n][i] ? mx : dp[n][i];
	}
	cout << mx;
	return 0;
}