글 읽기 - 아래 코드의 시간복잡도가 궁금합니다.

kth990303 2년 전 1

KCM Travel 문제처럼 dijkstra로 접근하되,

최단경로 문제가 아니기 때문에 우선순위 큐 operator() 를 아래와 같이

리프트횟수를 최소인 우선순위로, 거리를 최대인 우선순위로 우선순위큐 cmp를 설정하여 접근해보았습니다.

O(10*2*MlgN)일 줄 알았는데 시간초과가 나더라구요.

우선순위 큐 cmp를 다르게 설정하여 다익스트라로 풀리지 않는 이유(시간초과가 나는 이유)가 궁금합니다.

#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<pl, ll> pll;
const int MAX = 100001;
const int MAXT = 11;
const ll INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
ll N, M, K, S, T, ans = -1, d[MAX][MAXT];
vector<pll> v[MAX];
struct cmp {
   bool operator()(pll p1, pll p2) {
       // 리프트 횟수가 같다면, 거리가 최대가 되도록 우선순위큐를 설정한다.
      if (p1.first.first == p2.first.first)
         return p1.second < p2.second;
      // 리프트 횟수를 최소인 것 우선순위
      return p1.first.first > p2.first.first;
   }
};
int main() {
   cin.tie(0)->sync_with_stdio(0);

   cin >> N >> M >> K >> S >> T;
   while (M--) {
      ll a, b, t;
      cin >> a >> b >> t;
      v[a].push_back({ {0, b}, t });
      // 반대방향은 리프트 횟수가 1, 거리는 올라가지 않으므로 0
      v[b].push_back({ {1, a}, 0 });
   }
   memset(d, -1, sizeof(d));
   priority_queue<pll, vector<pll>, cmp> pq;
   pq.push({ {0, S}, 0 });
   d[S][0] = 0;
   // 다익스트라로 접근하되, 우선순위큐 조건 변경해서 최대힙으로 접근
   while (!pq.empty()) {
      ll time = pq.top().first.first;
      ll cur = pq.top().first.second;
      ll cost = pq.top().second;
      pq.pop();
      // 리프트 횟수(time)이 K 이하일 때만 파악하면 됨.
      if (time > K || d[cur][time] > cost)
         continue;
      for (auto i : v[cur]) {
         ll nTime = i.first.first + time;
         ll next = i.first.second;
         ll nCost = i.second + cost;
         if (nTime <= K && nCost > d[next][nTime]) {
            // dp (리프트 횟수가 K 이상인 것들은 nCost 최대로 올려줌)
            for (int j = nTime; j <= K; j++) {
               if (d[next][j] >= nCost)
                  break;
               d[next][j] = nCost;
            }
            pq.push({ {nTime, next}, nCost });
         }
      }
   }
   for (int i = 0; i <= K; i++) {
      ans = max(ans, d[T][i]);
   }
   cout << ans << "\n";
}

kth990303 2년 전 0

아직 완전히 감이 잡히지는 않았지만 슬랙에서 많은 분들이 도움을 주셔서 다른 분들도 보실 수 있게 댓글로 남깁니다 :)

1. 음수 간선이 존재하거나

2. 최장거리를 구하는 문제에선

다익스트라 알고리즘이 제대로 돌아가지 않을 수 있으며, 실제로 최장거리를 구하는 문제는 NP-Hard라고 합니다.

lky님께서 남겨주신 링크: https://en.wikipedia.org/wiki/Longest_path_problem

이 문제에서 K가 10 이하이고, 리프트를 제외하곤 DAG라서 가능하지 않을까 했는데.. 아직 완전히 감이 잡히진 않지만 좀 더 공부해봐야겠습니다 :)

슬랙에 도움주신 분들 모두 감사드립니다.

kth990303 2년 전 0

최장거리를 다익스트라로 해결할 경우:

최단거리를 다익으로 해결할 때와 달리, 지금까지 연결된 거리에서 더 앞으로 나아가는 것이 무조건 최적해이므로 끝까지 돌게 되며, 이후에 알고보니 다른 정점을 통해 도달하는 것이 더 먼경우, 그 정점을 통해 또 끝까지 돌게 되고... 이런 식으로 반복해서 될 수 있기 때문에 NP-Hard가 됨을 djm03178님께서 슬랙에서 추가적으로 설명해주셨습니다.

덕분에 다익스트라가 안되는 이유를 보다 명확하게 알게 됐습니다 다들 감사드립니다 :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

아래 코드의 시간복잡도가 궁금합니다.

kth990303 2년 전 1

kth990303 2년 전 0

kth990303 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말