Submission #132657

#	Time	Username	Problem	Language	Result	Execution time	Memory
132657		arman_ferdous	Cities (BOI16_cities)	C++17	100 / 100	3217 ms	46696 KiB

cities

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<ll,int>;
const int N = 1e5+100;
const int M = 2e5+100;
const ll oo = 1e18;

int n, k, m, sp[5];
ll dp[40][N];
vector<ii> g[N];
priority_queue<ii,vector<ii>,greater<ii>> q;

int main() {
	scanf("%d %d %d", &n, &k, &m);
	for(int i = 0; i < k; i++)
		scanf("%d", &sp[i]);
	for(int i = 0; i < m; i++) {
		int u, v; ll w;
		scanf("%d %d %lld", &u, &v, &w);
		g[u].push_back({w, v});
		g[v].push_back({w, u});
	}
	for(int i = 0; i < (1 << k); i++)
		for(int j = 1; j <= n; j++)
			dp[i][j] = oo;
	for(int i = 0; i < k; i++)
		dp[(1 << i)][sp[i]] = 0;

	for(int mask = 1; mask < (1 << k); mask++) {
		for(int c = 0; c < mask; c++) {
			if((mask & c) == c) {
				for(int i = 1; i <= n; i++) 
					dp[mask][i] = min(dp[mask][i], dp[c][i] + dp[(c ^ mask)][i]);
			}
		}
		for(int i = 1; i <= n; i++) if(dp[mask][i] < oo) 
			q.push({dp[mask][i], i});
		while(!q.empty()) {
			int u = q.top().second;
			ll cw = q.top().first; q.pop();
			for(auto e : g[u]) {
				int v = e.second; ll w = e.first;
				if(dp[mask][v] > cw + w) {
					dp[mask][v] = cw + w;
					q.push({dp[mask][v], v});
				}
			}
		}
	}
	ll ans = oo;
	for(int i = 1; i <= n; i++)
		ans = min(ans, dp[(1 << k) - 1][i]);
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:16: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:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &sp[i]);
   ~~~~~^~~~~~~~~~~~~~
cities.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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