BOJ 13907 : 세금

13907번: 세금 (acmicpc.net)

13907번: 세금

 

 

시간 복잡도:

• O(N^2logN + NK)

 

알고리즘:

• 다익스트라
• 최적화

 

예제 힌트를 보고 깨달으셨을 것입니다. 이 문제는 일반적인 최단 거리 알고리즘으로 풀어서는 안 됩니다. 따라서 저희는 이렇게 접근할 수 있습니다: "최단거리가 바뀌는 조건은 무엇일까?"

 

최단거리가 바뀌는 조건을 한 번 찾아봅시다. 힌트에서 보듯, 세금이 j만큼 인상할 때마다, 1->2->3 경로는 총 2 * j 만큼의 가격이 인상했고, 1->3 경로는 j만큼 증가했음을 알 수 있습니다. 이를 보면, 거리의 수와 인과관계가 있다고 알 수 있습니다.

이제 이를 풀이에 인용해봅시다. 다익스트라를 2차원으로 설정해서,

 

• D[i][j] = i번째 노드로 j만큼의 간선을 거쳐서 가는 최단거리

 

라고 설정한 후, 다익스트라 알고리즘을 인용할 수 있습니다. 그런데, 이렇게 하면, O(NMlogN)의 알고리즘으로, 시간 초과가 나게 됩니다. 따라서, 최적화를 해야 합니다.

 

S->D로 가는 경로 중, 갔던 정점을 다시 가는 경로가 있다고 해 봅시다. 그리고 그 경로의 간선 개수를 R 개라고 합시다. 먼저, 이는 어떤 조건에도 최단경로가 될 수 없습니다. 세금이 10억이나 인상해도, 그 경로는 최단경로가 될 수 없다는 말입니다.

왜냐하면, R보다 적은 간선을 거치는 최단경로에 의해 복속되기 때문이죠. 이는 어찌 보면 당연한데, 글로만 설명하면 힘드니 그림으로 보겠습니다.

 

 

 

 

자, 이제 좀 감이 오실 것입니다. S->D로 가는 경로 중 다이렉트로 가는 경로가 있고, v1, v2를 거치는 경로가 있습니다. 세금이 얼마가 인상되든 간에, v1, v2를 거치는 길은 다이렉트보다 더 비용이 많이 나갑니다.

 

예상하셨듯 이러한 문제는 간선을 N개 이상 방문할 때 나타납니다. 따라서 j가 1~N-1일 때만 체크해 주면 됩니다.

 

마지막은 간단합니다. 각 쿼리마다 최댓값 업데이트 및 찾기를 수행하면, O(NK)로 아슬아슬하게 통과할 수 있습니다. cin, cout을 사용할 때 개행 문자 및 전처리를 해야 시간 초과가 안 나니 주의하세요.

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
#define pp pair<int, int>
#define ppp pair<int, pp>
#define INF 1234567890

int N, M, K, S, DEST;
vector<pp> graph[1001];
int D[1001][1001];

int main() {

  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  cin >> N >> M >> K >> S >> DEST;
  for (int i = 0; i < M; i++) {
    int from, to, cost;
    cin >> from >> to >> cost;
    graph[from].push_back({to, cost});
    graph[to].push_back({from, cost});
  }

  for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= N; j++) {
      if (j == N) D[i][j] = -INF;
      else D[i][j] = INF;
    }
  }

  priority_queue<ppp, vector<ppp>, greater<ppp> > pq; // cost, idx, edges
  D[S][0] = 0;
  pq.push({ 0, {S, 0} });

  while (!pq.empty()) {
    int idx = pq.top().second.first;
    int edges = pq.top().second.second;
    int cost = pq.top().first;
    pq.pop();

    if (D[idx][edges] < cost) continue;

    for (int i = 0; i < graph[idx].size(); i++) {
      int nxt = graph[idx][i].first;
      int dist = graph[idx][i].second + cost;

      if (D[nxt][edges + 1] > dist) {
        D[nxt][edges + 1] = dist;
        pq.push({ dist, {nxt, edges + 1}});
      }
    }
  }

  int minii = INF;
  for (int j = 1; j < N; j++) { minii = min(minii, D[DEST][j]); }
  cout << minii << '\n';

  for (int i = 0; i < K; i++) {
    int increase; cin >> increase;

    int mini = INF;
    for (int j = 1; j < N; j++) {
      D[DEST][j] += increase * j;
      mini = min(mini, D[DEST][j]);
    }

    cout << mini << '\n';
  }
}