oj.uz

Submission #335027

# Submission time Handle Problem Language Result Execution time Memory
335027 2020-12-10T20:37:26 Z limabeans Cities (BOI16_cities) C++17
100 / 100
 3962 ms 52264 KB 
#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=1; 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.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 47816 KB Output is correct
2 Correct 806 ms 47104 KB Output is correct
3 Correct 494 ms 39800 KB Output is correct
4 Correct 80 ms 12068 KB Output is correct
5 Correct 398 ms 45464 KB Output is correct
6 Correct 75 ms 12012 KB Output is correct
7 Correct 5 ms 3180 KB Output is correct
8 Correct 3 ms 3052 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3180 KB Output is correct
2 Correct 7 ms 3180 KB Output is correct
3 Correct 7 ms 3052 KB Output is correct
4 Correct 5 ms 3052 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1737 ms 47612 KB Output is correct
2 Correct 1736 ms 51512 KB Output is correct
3 Correct 1169 ms 42028 KB Output is correct
4 Correct 957 ms 35188 KB Output is correct
5 Correct 220 ms 19524 KB Output is correct
6 Correct 90 ms 17644 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3912 ms 47636 KB Output is correct
2 Correct 3957 ms 52264 KB Output is correct
3 Correct 3962 ms 51416 KB Output is correct
4 Correct 2848 ms 42288 KB Output is correct
5 Correct 2052 ms 35312 KB Output is correct
6 Correct 352 ms 19560 KB Output is correct
7 Correct 109 ms 17772 KB Output is correct