oj.uz

Submission #60646

# Submission time Handle Problem Language Result Execution time Memory
60646 2018-07-24T13:05:01 Z tmwilliamlin168 Cities (BOI16_cities) C++14
100 / 100
 3631 ms 88152 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pli pair<ll, int>
#define fi first
#define se second

const int mxN=1e5, mxK=5;
int n, k, m, a[mxK];
vector<pli> adj[mxN];
ll dist[1<<mxK][mxN], ans=LLONG_MAX;
priority_queue<pli, vector<pli>, greater<pli>> pq;

inline void dijkstra(ll dist[mxN]) {
	for(int i=0; i<n; ++i)
		pq.push({dist[i], i});
	while(!pq.empty()) {
		pli p=pq.top();
		pq.pop();
		int u=p.se;
		if(p.fi>dist[u])
			continue;
		for(pli e : adj[u]) {
			int v=e.se;
			if(dist[u]+e.fi<dist[v]) {
				dist[v]=dist[u]+e.fi;
				pq.push({dist[v], v});
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k >> m;
	for(int i=0; i<k; ++i)
		cin >> a[i], --a[i];
	while(m--) {
		int u, v, w;
		cin >> u >> v >> w, --u, --v;
		adj[u].push_back({w, v});
		adj[v].push_back({w, u});
	}
	for(int i=0; i<k; ++i) {
		memset(dist[1<<i], 0x3F, 8*n);
		dist[1<<i][a[i]]=0;
	}
	for(int i=1; i<1<<k; ++i) {
		if(__builtin_popcount(i)>1) {
			memset(dist[i], 0x3F, 8*n);
			for(int j=0; j<k; ++j)
				if(i>>j&1)
					for(int l=0; l<n; ++l)
						dist[i][l]=min(dist[i^1<<j][l]+dist[1<<j][l], dist[i][l]);
		}
		dijkstra(dist[i]);
	}
	for(int i=0; i<n; ++i)
		ans=min(dist[(1<<k)-1][i], ans);
	cout << ans;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2680 KB Output is correct
2 Correct 5 ms 2920 KB Output is correct
3 Correct 4 ms 2920 KB Output is correct
4 Correct 6 ms 2928 KB Output is correct
5 Correct 6 ms 3008 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1165 ms 25648 KB Output is correct
2 Correct 908 ms 29476 KB Output is correct
3 Correct 707 ms 29476 KB Output is correct
4 Correct 139 ms 29476 KB Output is correct
5 Correct 627 ms 37416 KB Output is correct
6 Correct 115 ms 37416 KB Output is correct
7 Correct 11 ms 37416 KB Output is correct
8 Correct 8 ms 37416 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 37416 KB Output is correct
2 Correct 12 ms 37416 KB Output is correct
3 Correct 9 ms 37416 KB Output is correct
4 Correct 11 ms 37416 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1904 ms 54124 KB Output is correct
2 Correct 1908 ms 57556 KB Output is correct
3 Correct 1460 ms 57556 KB Output is correct
4 Correct 1186 ms 57856 KB Output is correct
5 Correct 338 ms 57856 KB Output is correct
6 Correct 139 ms 57964 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3580 ms 88076 KB Output is correct
2 Correct 3481 ms 88152 KB Output is correct
3 Correct 3631 ms 88152 KB Output is correct
4 Correct 2872 ms 88152 KB Output is correct
5 Correct 1880 ms 88152 KB Output is correct
6 Correct 470 ms 88152 KB Output is correct
7 Correct 207 ms 88152 KB Output is correct