Submission #117155

#	Time	Username	Problem	Language	Result	Execution time	Memory
117155		Just_Solve_The_Problem	Cities (BOI16_cities)	C++11	100 / 100	4663 ms	57428 KiB

cities

#include <bits/stdc++.h>

#define ll long long
#define ok puts("ok");

using namespace std;

const int N = (int)1e5 + 7;
const ll linf = (ll)1e18 + 7;

int n, k, m;
vector <pair<int, int>> gr[N];
vector <int> sp;
ll ans = 1e18;

map <pair<int, int>, int> mp;

ll dp[N][1 << 5];

main() {
	for (int i = 0; i < 32; i++) {
		for (int j = 0; j < N; j++) {
			dp[j][i] = linf;
		}
	}
	scanf("%d %d %d", &n, &k, &m);
	for (int i = 1, x; i <= k; i++) {
		scanf("%d", &x);
		sp.push_back(x);
		dp[x][1 << (i - 1)] = 0;
	}
	for (int i = 1, u, v, w; i <= m; i++) {
		scanf("%d %d %d", &u, &v, &w);
		if (u == v) continue;
		if (u > v) swap(u, v);
		if (!mp.count({u, v})) mp[{u, v}] = w;
		else mp[{u, v}] = min(w, mp[{u, v}]);
	}
	for (auto to : mp) {
		int u, v, w;
		u = to.first.first;
		v = to.first.second;
		w = to.second;
		gr[u].push_back({v, w});
		gr[v].push_back({u, w});
	}
	
	for (int mask = 1; mask < (1 << k); mask++) {
		int nx = mask;
		while (nx) {
			nx = (nx - 1) & mask;
			if (nx == 0) break;
			for (int i = 1; i <= n; i++) {
				dp[i][mask] = min(dp[i][mask], dp[i][mask ^ nx] + dp[i][nx]);
			}
		} 
		priority_queue <pair<ll, int>> q;
		for (int i = 1; i <= n; i++) {
			q.push({-dp[i][mask], i});
		}
		while (!q.empty()) {
			ll cur = -q.top().first;
			int v = q.top().second;
			q.pop();
			if (cur > dp[v][mask]) continue;
			for (auto id : gr[v]) {
				int to = id.first;
				int w = id.second;
				if (cur + w < dp[to][mask]) {
					dp[to][mask] = cur + w;
					q.push({-dp[to][mask], to});
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		ans = min(ans, dp[i][(1 << k) - 1]);
	}
	cout << ans << endl;
}

Compilation message (stderr)

cities.cpp:20:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
cities.cpp: In function 'int main()':
cities.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &k, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
cities.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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