oj.uz

Submission #94778

# Submission time Handle Problem Language Result Execution time Memory
94778 2019-01-23T17:16:53 Z popovicirobert Cities (BOI16_cities) C++14
100 / 100
 2661 ms 45060 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const ll INF = 1e18;
const int MAXN = (int) 1e5;
const int MAXK = 5;

vector < pair <int, int> > g[MAXN + 1];

ll dp[1 << MAXK][MAXN + 1], dist[MAXN + 1];
bool vis[MAXN + 1];
int nodes[MAXK];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, k, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> k >> m;
    for(int conf = 1; conf < (1 << k); conf++) {
        for(i = 1; i <= n; i++) {
            dp[conf][i] = INF;
        }
    }
    for(i = 0; i < k; i++) {
        cin >> nodes[i];
        dp[1 << i][nodes[i]] = 0;
    }
    for(i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    for(int conf = 1; conf < (1 << k); conf++) {
        priority_queue < pair <ll, int> > pq;
        for(i = 1; i <= n; i++) {
            dist[i] = INF;
            vis[i] = 0;
            for(int cnf = 0; cnf < conf; cnf++) {
                if((conf & cnf) == cnf) {
                    dp[conf][i] = min(dp[conf][i], dp[cnf][i] + dp[conf ^ cnf][i]);
                }
            }
            pq.push({-dp[conf][i], i});
        }
        while(pq.size()) {
            pair <ll, int> cur = pq.top();
            cur.first *= -1;
            pq.pop();
            if(vis[cur.second]) {
                continue;
            }
            vis[cur.second] = 1;
            dp[conf][cur.second] = cur.first;
            for(auto it : g[cur.second]) {
                if(dp[conf][it.first] > cur.first + it.second) {
                    dp[conf][it.first] = cur.first + it.second;
                    pq.push({-cur.first - it.second, it.first});
                }
            }
        }
    }
    ll ans = INF;
    for(i = 1; i <= n; i++) {
        ans = min(ans, dp[(1 << k) - 1][i]);
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 3 ms 2808 KB Output is correct
5 Correct 3 ms 2808 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 26196 KB Output is correct
2 Correct 708 ms 26168 KB Output is correct
3 Correct 468 ms 17932 KB Output is correct
4 Correct 71 ms 10912 KB Output is correct
5 Correct 341 ms 22996 KB Output is correct
6 Correct 70 ms 10784 KB Output is correct
7 Correct 7 ms 2936 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3064 KB Output is correct
2 Correct 9 ms 3064 KB Output is correct
3 Correct 7 ms 2936 KB Output is correct
4 Correct 7 ms 2936 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1222 ms 32416 KB Output is correct
2 Correct 1207 ms 32552 KB Output is correct
3 Correct 877 ms 24324 KB Output is correct
4 Correct 643 ms 22704 KB Output is correct
5 Correct 193 ms 14300 KB Output is correct
6 Correct 76 ms 12588 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2661 ms 45060 KB Output is correct
2 Correct 2465 ms 45056 KB Output is correct
3 Correct 2549 ms 44944 KB Output is correct
4 Correct 2180 ms 36956 KB Output is correct
5 Correct 1358 ms 29160 KB Output is correct
6 Correct 252 ms 15576 KB Output is correct
7 Correct 92 ms 12892 KB Output is correct