Submission #94778

#	Time	Username	Problem	Language	Result	Execution time	Memory
94778		popovicirobert	Cities (BOI16_cities)	C++14	100 / 100	2661 ms	45060 KiB

cities

#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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26