BOJ 9446 - 아이템 제작

BOJ 9446 - 아이템 제작

처음엔 그냥 그래프 + DP 인줄 알고 풀었다가 바로 틀렸다.

좀 생각해보니 최단거리 알고리즘으로 풀면 되겠다 싶었다.

최단거리 알고리즘이 사실 그래프 + DP이긴 하다.

간선을 다음과 같이 생각하자.

현재 노드가 $x$라면, $x+y \to a$ 가 되는 조합법이 있다고 하면 $(y,a)$ 간선을 관리한다.

이 간선의 총 개수는 여전히 $M$이다.

큐에서 꺼내졌을 때, 간선 중 $d_x+d_y < d_a$ 인 경우가 존재한다면 $d_a$를 업데이트 해주고 큐에 넣어주는 것으로 완전히 다익스트라처럼 돌려주면 된다.

다익스트라의 시간복잡도는 $O(E \log V)$ 이다. 따라서 시간안에 돈다.

대신, 한 정점을 처음에 큐에 넣는게 아닌 $2 \sim N$ 번 정점들을 모두 넣어주고 $1$번 정점의 최종 값을 확인하면 된다.

const int inf = 2e15;  
void solve() {  
   int n, m;  
   cin >> n >> m;  
   vi c(n);  
   vector<vector<pi>> recipe(n);  
   vector<vector<pi>> edges(n);  
   fv(c);  
   for (int i = 0; i < m; i++) {  
      int a, x, y;  
      cin >> a >> x >> y, a--, x--, y--;  
      recipe[a].pb({x, y});  
      edges[x].pb({y, a});  
      edges[y].pb({x, a});  
      c[a] = min(c[a], c[x] + c[y]);  
   }  
   priority_queue<pi, vector<pi>, greater<>> pq;  
   for (int i = 1; i < n; i++) pq.push({c[i], i});  
   while (sz(pq)) {  
      auto [cur_d, cur] = pq.top();  
      pq.pop();  
      if (c[cur] < cur_d) continue;  
  
      for (const auto &[with, to]: edges[cur]) {  
         if (c[to] > c[with] + cur_d) {  
            pq.push({c[to] = c[with] + cur_d, to});  
         }  
      }  
   }  
   cout << c[0];  
}