minimizing_coins_1634.cpp (606B)
1 #include <algorithm> 2 #include <iostream> 3 #include <queue> 4 #include <vector> 5 6 int f(const std::vector<int>& c, int x) { 7 static constexpr int max = 999999999; 8 std::vector<int> a(x+1, max); 9 std::queue<int> q; 10 a[0] = 0; 11 q.push(0); 12 while (!q.empty()) { 13 auto i = q.front(); 14 q.pop(); 15 for (auto k : c) { 16 if (i + k > x || a[i+k] <= a[i]+1) continue; 17 if (i + k == x) return a[i] + 1; 18 a[i+k] = a[i] + 1; 19 q.push(i + k); 20 } 21 } 22 return -1; 23 } 24 25 int main() { 26 int n, x; 27 std::cin >> n >> x; 28 std::vector<int> c(n); 29 for (int i = 0; i < n; i++) 30 std::cin >> c[i]; 31 32 std::cout << f(c, x) << "\n"; 33 }