[ Baekjoon ] 10217. KCM Travel

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

10217번: KCM Travel

풀이 방법

소요시간을 기준으로 다익스트라 알고리즘을 적용해 풀 수 있다. 이때, 지원비용 내에서 최소 소요시간을 구하는 문제이기 때문에 한번 방문했던 vertex더라도 재방문할 수 있다(소요시간은 짧지만 비용이 커서 해당 경로로 못 갈 수 있기 때문이다). 

 

처음엔 다익스트라 알고리즘에서 인접 vertex에 대해 distance 벡터를 업데이트해줄 때 다음과 같이 조건을 변형했었다. 이전에 방문한 적이 있는 vertex에 대해서는 distance 벡터를 업데이트해줄 수 없기 때문에 방문한 적이 있다면 무조건 재방문을 허용했는데, 이렇게 구현하니 우선순위 큐에서 메모리 초과가 발생했다.

for(auto e: adj[cur]){
	if(dist[e.v] > dist[cur] + e.time || visit[e.v]){
		dist[e.v] = dist[cur] + e.time;
		pq.emplace(dist[e.v], total_cost + e.cost, e.v);
	}
}

 

구글링을 통해 DP로 푸는 방법을 알아내었다. distance 벡터에 각 노드까지 도착하는 최소 시간을 업데이트 하는 게 아니라, 다음과 같이 각 노드까지 도착하는 비용에 대하여 최소 시간을 업데이트해나간다. 그 후, 도착 지점에서 비용에 상관없이(무조건 지원비용 범위 내의 비용이다) 최소 시간을 반환한다.

// min_time[i][j]: 노드 i까지 j원으로 도착하는 최소 시간
int min_time[N+1][budget+1]; 

// update distance vector
for(auto e: adj[cur]){
	int c = total_cost + e.cost;
	if(c <= budget){
		if(min_time[e.v][c] > min_time[cur][total_cost] + e.time){
			min_time[e.v][c] = min_time[cur][total_cost] + e.time;
			pq.emplace(min_time[e.v][c], c, next);
		}
	}
}

 

전체 코드는 여기서 확인할 수 있다.