[12913번] 매직 포션

문제 출처 :

https://www.acmicpc.net/problem/12913

알고리즘 분석 :

문제 해결에 필요한 사항

1. 다익스트라 알고리즘

2. 우선순위 큐

다익스트라를 기본으로 이용하고 dist 배열을 응용해준다.

포션을 이용할 수 있다면 포션을 이용한 값을 dist[next][potion - 1]으로 갱신하고 우선순위 큐에 넣거나,

포션을 이용할 수 없다고 포션을 이용하지 않고 움직인 값을 dist[next][potion]으로 갱신하며 문제를 풀면 해결 할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <queue> #include <functional>   using namespace std;   typedef pair<int, double> pid; typedef pair<double, int> pdi;   vector<pid> vc[52]; double dist[52][52];   int main() {     int n, k;     scanf("%d %d", &n, &k);       for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++)         {             int val;             scanf("%1d", &val);               if (i == j)                 continue;             vc[i].push_back({ j, 1.0*val });             vc[j].push_back({ i, 1.0*val });         }       for (int i = 0; i < 52; i++)         for (int j = 0; j < 52; j++)             dist[i][j] = 987654.0;       priority_queue<pair<pdi, int>, vector<pair<pdi, int> >, greater<> > pq;     pq.push({ { 0.0, 0 }, k });       double ans = 987654.0;     while (!pq.empty())     {         double cost = pq.top().first.first;         int here = pq.top().first.second;         int potion = pq.top().second;         pq.pop();           if (cost > dist[here][potion])             continue;           if (here == 1)             ans = min(ans, cost);                  for (int i = 0; i < vc[here].size(); i++)         {             if (potion - 1 >= 0)             {                 int next = vc[here][i].first;                 double nextCost = vc[here][i].second / 2 + cost;                   if (nextCost < dist[next][potion - 1])                 {                     dist[next][potion - 1] = nextCost;                     pq.push({ {nextCost, next}, potion - 1});                 }             }               int next = vc[here][i].first;             double nextCost = vc[here][i].second + cost;                      if (nextCost < dist[next][potion])             {                 dist[next][potion] = nextCost;                 pq.push({ { nextCost, next }, potion});             }                      }     }       printf("%.9lf", ans);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus