Submission #1130665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130665		Skymagic	Cities (BOI16_cities)	C++17	100 / 100	1700 ms	37436 KiB

cities

/********************
 * what  the  sigma *
 * this code has been stolen muhahaha *
 ********************/
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define ve vector
#define ll long long
#define ld long double
#define db(x) cout << "Debug at " << x << endl;
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int, int>
#define tii tuple<ll,int,int>
#define pll pair<ll,int>
#define sz(x) (int)x.size()
#define pb push_back
const ll mod = 1e9+7,maxn=100005;
const ll INF=(ll)1e18;
vector<pii> adj[maxn];
ll dis[32][maxn];
int n,k,m,pos[6];
priority_queue<pll,ve<pll>,greater<pll>> pq;
void dijkstra(int mask) {
    for (int i=1;i<=n;i++) if (dis[mask][i]<INF) pq.push({dis[mask][i], i});
    while (!pq.empty()) {
        auto [len, u] = pq.top(); pq.pop();
        if (dis[mask][u]!=len) continue;
        for (auto [v, w]:adj[u]) if (dis[mask][v]>len+w) {
            dis[mask][v]=len+w;
            pq.push({dis[mask][v],v});
        }
    }
}
int main() {
    lgm;
    cin >> n >> k >> m;
    for (int i=1;i<=k;i++) cin >> pos[i];
    int u, v, w;
    for (int i=1;i<=m;i++) {
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int mask=1;mask<(1<<k);mask++) for (int i=1;i<=n;i++) dis[mask][i] = INF;
    for (int i=1;i<=k;i++) dis[(1<<(i-1))][pos[i]]=0;
    for (int mask=1;mask<(1<<k);mask++) {
        for (int i=1;i<=n;i++)
            for (int smask=mask;smask>0;smask=(smask-1)&mask)
                dis[mask][i]=min(dis[mask][i],dis[smask][i]+dis[mask^smask][i]);
        dijkstra(mask);
    }
    cout << *min_element(dis[(1<<k)-1]+1,dis[(1<<k)-1]+n+1);
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26