oj.uz

Submission #105993

# Submission time Handle Problem Language Result Execution time Memory
105993 2019-04-16T06:04:01 Z xiaowuc1 Cities (BOI16_cities) C++14
100 / 100
 4468 ms 45096 KB 
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef vector<vector<ll>> matrix;

int n, k, m;
int important[5];
vector<pii> edges[100005];
ll dp[100005][32];

void relax(int mask) {
	for(int i = 1; i <= n; i++) {
		int j = mask;
		while(j > 0) {
			dp[i][mask] = min(dp[i][mask], dp[i][j] + dp[i][j^mask]);
			j = (j-1) & mask;
		}
	}
	priority_queue<plli> q;
	for(int i = 1; i <= n; i++) {
		q.push({-dp[i][mask], i});
	}
	while(!q.empty()) {
		plli curr = q.top();
		q.pop();
		if(-curr.first != dp[curr.second][mask]) continue;
		for(pii out: edges[curr.second]) {
			int nextD = out.first;
			ll nextW = -curr.first + out.second;
			if(dp[nextD][mask] > nextW) {
				dp[nextD][mask] = nextW;
				q.push({-dp[nextD][mask], nextD});
			}
		}
	}
}

// init 1-bit
void dijkstra() {
	for(int i = 0; i < k; i++) {
		priority_queue<plli> q;
		q.push({0, important[i]});
		dp[important[i]][1<<i] = 0;
		while(!q.empty()) {
			plli curr = q.top();
			q.pop();
			if(-curr.first != dp[curr.second][1<<i]) continue;
			for(pii out: edges[curr.second]) {
				int nextD = out.first;
				ll nextW = -curr.first + out.second;
				if(dp[nextD][1<<i] > nextW) {
					dp[nextD][1<<i] = nextW;
					q.push({-dp[nextD][1<<i], nextD});
				}
			}
		}
	}
}

void solve() {
	cin >> n >> k >> m;
	for(int i = 1; i <= n; i++) {
		for(int a = 1; a < (1<<k); a++) {
			dp[i][a] = 1e18;
		}
	}
	for(int i = 0; i < k; i++) cin >> important[i];
	while(m--) {
		int a, b, c;
		cin >> a >> b >> c;
		edges[a].push_back({b, c});
		edges[b].push_back({a, c});
	}
	dijkstra();
	for(int mask = 3; mask < (1<<k); mask++) relax(mask);
	ll ret = 1e18;
	for(int i = 1; i <= n; i++) {
		ret = min(ret, dp[i][(1<<k)-1]);
	}
	cout << ret << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
	/*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
	*/
	solve();
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1046 ms 44720 KB Output is correct
2 Correct 1018 ms 44772 KB Output is correct
3 Correct 696 ms 36760 KB Output is correct
4 Correct 103 ms 11128 KB Output is correct
5 Correct 472 ms 42676 KB Output is correct
6 Correct 76 ms 11056 KB Output is correct
7 Correct 9 ms 3072 KB Output is correct
8 Correct 6 ms 3072 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3072 KB Output is correct
2 Correct 10 ms 3044 KB Output is correct
3 Correct 9 ms 3072 KB Output is correct
4 Correct 7 ms 2944 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2189 ms 44812 KB Output is correct
2 Correct 2145 ms 44772 KB Output is correct
3 Correct 1467 ms 36900 KB Output is correct
4 Correct 1187 ms 28940 KB Output is correct
5 Correct 338 ms 14964 KB Output is correct
6 Correct 118 ms 12536 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4468 ms 45096 KB Output is correct
2 Correct 4317 ms 44816 KB Output is correct
3 Correct 4305 ms 44856 KB Output is correct
4 Correct 3086 ms 36920 KB Output is correct
5 Correct 2193 ms 28756 KB Output is correct
6 Correct 445 ms 14932 KB Output is correct
7 Correct 148 ms 12664 KB Output is correct