[정답이 아니라 풀이 기록입니다.]
여러 도시가 도로들로 연결되어 있다. 도로간의 통행료가 있고, 모든 도로의 통행료가 K번 Ki씩 오를때 S도시에서 D도시로 가는 최초의 최소비용과 인상후 최소비용은 얼마인가?
세금의 인상은 모든 도로(이하 간선)에 일괄적용됩니다.
생각해보면 최소비용의 증가량은 최소비용을 이루기 위해 통과한 간선의 수에 따라 변경됩니다.
즉, 최소비용이던 경로가 통과한 간선이 많다면 인상 이후에는 최소비용이 아니게 변경되고 다른 통과한 간선이 적은 경로가 최소비용이 될 수 있습니다.
그렇기에 통과한 간선의 수로 따로 최소비용을 구해야합니다.
일반적인 최소비용에서 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);
}
통과한 간선의 수에 따라 비용증가량이 달라진다는 것을 떠올리면 풀 수 있을 것 같습니다.
끝!