oj.uz

Submission #282043

# Submission time Handle Problem Language Result Execution time Memory
282043 2020-08-23T21:37:37 Z Blagojce Cities (BOI16_cities) C++11
100 / 100
 2410 ms 82364 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(v) begin(v), end(v)


using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;

ll const inf = 1e18;
ld const eps = 1e-13;
int const i_inf = 1e9;
int const mxn = 1e5;

mt19937 _rand(time(NULL));
clock_t _timer = clock();

int n, k, m;
int imp[5];
vector<pii> g[mxn];
ll dist[mxn][5];

void dijkstra(int u){
	pq <pair<ll, int> > Q;
	Q.push({0, imp[u]});
	bool proc[n];
	memset(proc, false, sizeof(proc));
	fr(i, 0, n){
		dist[i][u] = inf;
	}
	dist[imp[u]][u] = 0;
	
	while(!Q.empty()){
		int c = Q.top().nd;
		Q.pop();
		
		if(proc[c]) continue;
		proc[c] = true;
		
		for(auto e : g[c]){
			if(dist[c][u] + e.nd < dist[e.st][u]){
				dist[e.st][u] = dist[c][u] + e.nd;
				Q.push({-dist[e.st][u], e.st});
			}
		}
	}
}
ll SpiderMan(int u){
	ll dp[n][(1<<k)];
	fr(i, 0, n) fr(j, 0, (1<<k)) dp[i][j] = inf;
	
	bool proc[n][(1<<k)];
	memset(proc, false, sizeof(proc));
	
	dp[imp[u]][(1<<u)] = 0;
	pq<pair<ll, pair<int,int> > > Q;
	Q.push({0, {imp[u], (1<<u)}});
	while(!Q.empty()){
		int c = Q.top().nd.st;
		int mask = Q.top().nd.nd;
		if(mask == (1<<k)-1) return dp[c][mask];
		Q.pop();
	
		if(proc[c][mask]) continue;
		proc[c][mask] = true;
		
		//throw web
		fr(i, 0, k){
			if(mask&(1<<i)) continue;
			
			if(dp[c][mask] + dist[c][i] < dp[c][(mask|(1<<i))]){
				dp[c][(mask|(1<<i))] = dp[c][mask] + dist[c][i];
				Q.push({-dp[c][mask|(1<<i)], {c, (mask|(1<<i))}});
			}
		}
		//move to other node
		for(auto e : g[c]){
			if(dp[c][mask] + e.nd < dp[e.st][mask]){
				dp[e.st][mask] = dp[c][mask] + e.nd;
				Q.push({-dp[e.st][mask], {e.st, mask}});
			}
		}
	}	
	return inf;
}

void solve(){
	cin >> n >> k >> m;
	fr(i, 0, k){
		cin >> imp[i];
		--imp[i];
	}
	fr(i, 0, m){
		int u, v, c;
		cin >> u >> v >> c;
		--u, --v;
		g[u].pb({v, c});
		g[v].pb({u, c});
	}
	fr(i, 0, k){
		dijkstra(i);
	}	
	/*ll ans = inf;
	fr(i, 0, k){
		ans = min(ans, SpiderMan(i));
		
	}*/
	cout<<SpiderMan(0)<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 32552 KB Output is correct
2 Correct 574 ms 31608 KB Output is correct
3 Correct 184 ms 20032 KB Output is correct
4 Correct 71 ms 11952 KB Output is correct
5 Correct 322 ms 23616 KB Output is correct
6 Correct 68 ms 11704 KB Output is correct
7 Correct 4 ms 3072 KB Output is correct
8 Correct 3 ms 2944 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3200 KB Output is correct
2 Correct 6 ms 3200 KB Output is correct
3 Correct 3 ms 3072 KB Output is correct
4 Correct 4 ms 2944 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1243 ms 47736 KB Output is correct
2 Correct 1084 ms 46688 KB Output is correct
3 Correct 743 ms 42448 KB Output is correct
4 Correct 647 ms 30696 KB Output is correct
5 Correct 143 ms 17524 KB Output is correct
6 Correct 77 ms 14200 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2349 ms 78236 KB Output is correct
2 Correct 2410 ms 82364 KB Output is correct
3 Correct 2233 ms 81540 KB Output is correct
4 Correct 1025 ms 75172 KB Output is correct
5 Correct 1328 ms 49876 KB Output is correct
6 Correct 283 ms 22964 KB Output is correct
7 Correct 86 ms 17908 KB Output is correct