[BAE/<JOON> 문제풀이] 10217. KCM Travel

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

10217번: KCM Travel

재채점 터져서 다시 푸는데 너무 힘들었다.

 

핵심::

최적값이 아니어도 탐색 줄기를 유지해야하는 문제이다.
모든 최적값이 아닌 값들을 통과시키는 경우 TLE를 피할 수 없으므로,
최적값이 아닌 탐색들 중 유지시킬 줄기를 선택하는 기준을 정하는게 메인 아이디어인 문제이다. ( Simulate Anealing ? )

이 풀이에서는 [사용한 비용과 경과된 시간] 이 모두 기존 경로에 비해 더 좋은 선택지가 아닐 경우 무시한다.

풀이::

어떤 도착지 D 로 오는 여러 경로들을 사용한 비용과 경과된 시간 2가지 지표로 저장한다.

시간 단축을 위해 set 배열을 사용했다 ( dset[도착지] : 해당 정점까지 경로 목록의 비용/시간 쌍 ). 시간과 다르게 비용은 상한선이 정해져있으므로 dp 배열 구성은 dp[도착지][사용한 비용] 이다.

새로운 정점에 도착한 경우, 비용과 시간을 계산해 현재 경로의 탐색을 계속 유지할 것인지 여부를 탐색한다.

조건은 다음과 같다.

1. 비용이 m을 초과했는가?

  : 초과했을 경우 무조건 탐색 종료

2. 현재 정점까지 같은 비용을 사용해 더 빠른 시간에 도착한 경로가 있는가 ? dp[정점][현재 비용] <= 현재 시간 

  : 있을 경우 탐색 종료

3. 현재 정점에 도착하는 기존 경로 목록 중, 하나라도 현재 정점보다 시간 / 비용이 모두 우월한 경로가 있는가 ?
  : 있을 경우 탐색 종료

 

위 3가지 조건들 중 1, 2번은 일반적인 다익스트라에도 있는 평범한 조건이지만 3번 조건은 기존 경로를 전수조사하기 때문에 시간 초과의 위험이 크다. 따라서 set 을 활용해 기존 경로에 대한 검색과 갱신을 log n 으로 구현한다.

해당 과정은 아래과 같다.

 * dset : 시간을 기준으로 정렬

1. dset[정점] 이 비었는가 ?

    > dset 에 현재 경로 정보 삽입, 현재 경로 탐색 유지

2. dset[정점].upper_bound(현재 경로) 실행

    2 - 1. 결과가 dset[정점].begin() 인 경우 -> 가장 빠른 시간에 도착하는 정점

      > 경로 정보 삽입, 탐색 유지

    2 - 2. 그 외

      > dset에서 앞에 저장된 정점보다 비용이 적은 경우 -> 앞 경로보다 오래 걸리는 경로 중 가장 적은 비용 사용

          > 현재 경로 정보 삽입 및 탐색 유지
          > 앞 정점과 시간이 같은 경우 : 앞 정점과 적은 비용으로 같은 시간에 도착이 가능하므로 앞 경로는 앞으로 고려할 필요 없음

              > 앞 정점 삭제

 

위와 같이 경로 유지 결정 로직을 log n 으로 구현할 수 있다. 그리고 풀이쓰면서 생각해보니까 set 안써도 됐을것 같다.

 

느낀점::

테케 구해서 디버깅 안했으면 절대 못 풀었을 것 같다. 난 로직 잘 짰다고 생각하고 돌리는데 자꾸 pq에 중복경로가 생기더라..

 

코드::

/*
최적값이 아니어도 탐색 줄기를 유지해야하는 문제이다.
모든 최적값이 아닌 값들을 통과시키는 경우 TLE를 피할 수 없으므로,
최적값이 아닌 탐색들 중 유지시킬 줄기를 선택하는 기준을 정하는게 메인 아이디어인 문제이다.
거리를 오름차순으로 정렬했을 때 비용이 내림차순으로 정렬되어야한다. ( 인접 시 같은 값 허용하지 않음 )
현재 정점까지 올 수 있는 시간 비용 쌍을 적절하게 정렬하고 새로운 루트로 도착했을 때 정합성 여부를 검사하면 된다. ( 그게 어려움 )
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>

using namespace std;

struct cost {
	int d, t, p;
};

struct cmpt {
	bool operator () (const cost& a, const cost& b) const {
		if (a.t == b.t) {
			return a.p < b.p;
		}
		return a.t < b.t;
	}
};

struct cmpt2 {
	bool operator () (cost a, cost b) {
		if (a.t == b.t) {
			return a.p > b.p;
		}
		return a.t > b.t;
	}
};

bool cmpf(cost a, cost b) {
	if (a.t == b.t) {
		return a.p < b.p;
	}
	return a.t < b.t;
}

int main() {	
	//freopen("C:\\Users\\dskim\\Downloads\\10217.in", "r", stdin);
	//freopen("C:\\Users\\dskim\\Downloads\\10217-2\\10217\\big4.in", "r", stdin);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc; cin >> tc;
	while (tc--) {
		int n, m, k; cin >> n >> m >> k;
		vector<vector<cost>> arr(n + 1);
		for (int i = 1; i <= k; i++) {
			int s, d, p, t; cin >> s >> d >> p >> t;
			arr[s].push_back({ d, t, p });
		}		

		for (int i = 1; i <= n; i++) {
			sort(arr[i].begin(), arr[i].end(), cmpf);
		}

		priority_queue<cost, vector<cost>, cmpt2> pq;
		vector<vector<int>> dp(n + 1, vector<int>(m + 1, 2100000000));
		vector<set<cost, cmpt>> dset(n + 1);

		pq.push({ 1, 0, 0 });
		dp[1][0] = 0;
		dset[1].insert({ 1, 0, 0 });

		while (!pq.empty()) {
			const auto cur = pq.top(); pq.pop();
			if (dp[cur.d][cur.p] < cur.t) continue;
			if (cur.d == n) continue;			
			for (const auto& nx : arr[cur.d]) { // n lg n 
				if (cur.p + nx.p > m) continue;
				if (dp[nx.d][cur.p + nx.p] <= nx.t + cur.t) continue;
				dp[nx.d][cur.p + nx.p] = nx.t + cur.t;
				if (dset[nx.d].empty()) {
					pq.push({ nx.d, cur.t + nx.t, cur.p + nx.p });
					dset[nx.d].insert({ nx.d, cur.t + nx.t, cur.p + nx.p });
					continue;
				}
				auto ip = dset[nx.d].upper_bound({ nx.d, cur.t + nx.t, cur.p + nx.p });
				if (ip == dset[nx.d].begin()) {					
					pq.push({ nx.d, cur.t + nx.t, cur.p + nx.p });
					dset[nx.d].insert({ nx.d, cur.t + nx.t, cur.p + nx.p });
				}				
				else {
					if (std::prev(ip)->p > nx.p + cur.p) {
						if (std::prev(ip)->t == nx.t + cur.t) {
							dset[nx.d].erase(std::prev(ip));
						}
						pq.push({ nx.d, cur.t + nx.t, cur.p + nx.p });
						dset[nx.d].insert({ nx.d, cur.t + nx.t, cur.p + nx.p });
					}
				}				
			}
		}		
		int mn = 2100000000;

		for (int i = 1; i <= m; i++) {
			mn = mn < dp[n][i] ? mn : dp[n][i];
		}

		if (mn == 2100000000) {
			cout << "Poor KCM" << "\n";
		}
		else {
			cout << mn << "\n";
		}
	}

	return 0;
}