oj.uz

Submission #335028

# Submission time Handle Problem Language Result Execution time Memory
335028 2020-12-10T20:38:10 Z limabeans Cities (BOI16_cities) C++17
100 / 100
 3945 ms 47912 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=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.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 2668 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 825 ms 47544 KB Output is correct
2 Correct 823 ms 47168 KB Output is correct
3 Correct 508 ms 39800 KB Output is correct
4 Correct 92 ms 12068 KB Output is correct
5 Correct 409 ms 45464 KB Output is correct
6 Correct 75 ms 12064 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 8 ms 3180 KB Output is correct
2 Correct 7 ms 3180 KB Output is correct
3 Correct 6 ms 3052 KB Output is correct
4 Correct 5 ms 2924 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1746 ms 47912 KB Output is correct
2 Correct 1775 ms 47364 KB Output is correct
3 Correct 1175 ms 39944 KB Output is correct
4 Correct 974 ms 31020 KB Output is correct
5 Correct 216 ms 15372 KB Output is correct
6 Correct 86 ms 14220 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3913 ms 47652 KB Output is correct
2 Correct 3945 ms 47800 KB Output is correct
3 Correct 3914 ms 47476 KB Output is correct
4 Correct 2806 ms 40216 KB Output is correct
5 Correct 2063 ms 30956 KB Output is correct
6 Correct 341 ms 15492 KB Output is correct
7 Correct 106 ms 14316 KB Output is correct