Submission #282044

#	Time	Username	Problem	Language	Result	Execution time	Memory
282044		Blagojce	Cities (BOI16_cities)	C++11	100 / 100	4440 ms	94376 KiB

cities

#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<<min(SpiderMan(1), SpiderMan(0))<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

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