Submission #335028

#	Time	Username	Problem	Language	Result	Execution time	Memory
335028		limabeans	Cities (BOI16_cities)	C++17	100 / 100	3945 ms	47912 KiB

cities

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll inf = 1e18;
const int maxn = 1e5 + 5;


int n,k,m;
vector<pair<ll,int>> g[maxn];
vector<int> a;

ll dp[maxn][32];
bool done[maxn][32];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>k>>m;
    a.resize(k);
    for (int i=0; i<k; i++) {
	cin>>a[i];
	--a[i];
    }

    for (int i=0; i<m; i++) {
	int u,v,w; cin>>u>>v>>w;
	--u; --v;
	g[u].push_back({w,v});
	g[v].push_back({w,u});
    }


    for (int i=0; i<n; i++) {
	for (int mask=0; mask<1<<k; mask++) {
	    dp[i][mask]=inf;
	}
    }

    for (int i=0; i<k; i++) {
	dp[a[i]][1<<i]=0;
    }

    for (int mask=1; mask<1<<k; mask++) {
	for (int c=0; c<=mask; c++) {
	    if (c&mask) {
		for (int i=0; i<n; i++) {
		    dp[i][mask]=min(dp[i][mask], dp[i][c]+dp[i][c^mask]);
		}
	    }
	}

	priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
	for (int i=1; i<=n; i++) {
	    if (dp[i][mask]<inf) {
		pq.push({dp[i][mask],i});
	    }
	}
	while (pq.size()) {
	    auto cur = pq.top();
	    pq.pop();
	    int at = cur.second;
	    ll val = cur.first;
	    if (done[at][mask]) continue;
	    done[at][mask] = true;
	    for (auto ed: g[at]) {
		ll wei = ed.first;
		int to = ed.second;
		if (dp[to][mask] > val + wei) {
		    dp[to][mask] = val + wei;
		    pq.push({dp[to][mask],to});
		}
	    }
	}
    }


    ll res = inf;
    for (int i=0; i<n; i++) {
	res = min(res, dp[i][(1<<k)-1]);
    }

    cout<<res<<endl;    
    return 0;
}

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