[BOJ]13907 세금

[정답이 아니라 풀이 기록입니다.]

세금

여러 도시가 도로들로 연결되어 있다. 도로간의 통행료가 있고, 모든 도로의 통행료가 K번 Ki씩 오를때 S도시에서 D도시로 가는 최초의 최소비용과 인상후 최소비용은 얼마인가?

접근

1. 도시 간 도로는 양방향 도로입니다.
2. 트리구조가 아니고 도시 사이에 통행료가 두개 존재할 수도 있습니다.
3. 통행료 인상은 모든 도로에 일괄적용 됩니다.
4. 인상된 이후에 최소비용을 다시 구하기엔 시간이 부족합니다.

구현

세금 인상

세금의 인상은 모든 도로(이하 간선)에 일괄적용됩니다.

생각해보면 최소비용의 증가량은 최소비용을 이루기 위해 통과한 간선의 수에 따라 변경됩니다.

즉, 최소비용이던 경로가 통과한 간선이 많다면 인상 이후에는 최소비용이 아니게 변경되고 다른 통과한 간선이 적은 경로가 최소비용이 될 수 있습니다.

그렇기에 통과한 간선의 수로 따로 최소비용을 구해야합니다.
일반적인 최소비용에서 D[노드의 수]만큼 비용을 나타내는 배열을 만들어 사용했다면,
이 문제에서 여기에 통과한 간선의 수를 반영해 D[통과한 간선의 수][노드의 수]로 배열을 만들어 사용합니다.

최소 비용 구하기

최소 비용을 구하는데에는 우선순위 큐를 {비용, {통과한 간선의 수, 노드 번호}} 형태로 만들어 두고
처음에 {0,{0,시작점 번호}}를 우선순위 큐에 넣은 후 다익스트라를 통해 찾으면 됩니다.

이때 STL 우선순위큐는 내림차순이기에 greater를 사용해 오름차순으로 변경해 줘야합니다.

while (!pq.empty()) {
		int node = pq.top().second.second;//노드 번호
		long long value = pq.top().first;//비용
		int Count = pq.top().second.first;//통과한 간선의 수
		pq.pop();

		if (D[Count][node] < value) {
			continue;
		}

		for (int i = 0; i < v[node].size(); i++) {
			if (D[Count + 1][v[node][i].first] > value + v[node][i].second) {
				D[Count + 1][v[node][i].first] = value + v[node][i].second;
				pq.push({ D[Count + 1][v[node][i].first],{Count+1,v[node][i].first}});
			}
		}
	}

답 구하기

인상 전의 최소비용을 출력하고 이후 인상할때마다 답을 출력해야하는데,
통과한 간선의 수별로 비용이 여러개이기때문에 for문을 통해 최소값을 찾아야합니다.

인상 전의 비용은 for을 돌며 D[i][도착지 노드]의 최소값을 찾으면 되고,
인상 이후의 비용은 for을 돌며 D[i][도착지 노드]에 i*(인상 비용)을 더해준 후 최소값을 찾으면 됩니다.

long long Min = MAX;
	for (int j = 1; j <= n; j++) {
		Min = min(Min, D[j][e]);
	}
	printf("%lld\n", Min);
	for (int i = 1; i <= k; i++) {
		scanf("%d",&a);
		Min = MAX;
		for (int j = 1; j <= n; j++) {
			D[j][e] += (j*a);
			Min = min(Min, D[j][e]);
		}
		printf("%lld\n", Min);
	}

마무리

통과한 간선의 수에 따라 비용증가량이 달라진다는 것을 떠올리면 풀 수 있을 것 같습니다.

끝!