Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using std::cin;
- using std::cout;
- using std::vector;
- using std::pair;
- const long long INF = 1e18;
- bool isbit(long long mask, long long bit) {
- return (mask >> bit) & 1;
- }
- int main() {
- int n, m;
- cin >> n >> m;
- vector <long long> dist(n);
- vector<vector<long long> > cost(n, vector<long long> (m));
- for (int i = 0; i < n; ++i) {
- cin >> dist[i];
- for (int j = 0; j < m; ++j) {
- cin >> cost[i][j];
- }
- }
- vector<vector<long long> > dp(n, vector <long long> (1 << m, INF));
- for (int i = 0; i < n; ++i) {
- for (int mask = 1; mask < (1 << m); ++mask) {
- dp[i][mask] = dist[i];
- for (int k = 0; k < m; ++k) {
- if (isbit(mask, k)) {
- dp[i][mask] += cost[i][k];
- }
- }
- }
- }
- vector<long long> mini(1 << m, INF);
- for (int mask = 1; mask < (1 << m); ++mask) {
- for (int submask = mask; submask; submask = (submask - 1) & mask) {
- mini[mask] = std::min(mini[submask], mini[mask ^ submask]);
- }
- }
- std::cout << mini[(1 << m) - 1];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement