Submission #535492

#	Time	Username	Problem	Language	Result	Execution time	Memory
535492		ngpin04	Cities (BOI16_cities)	C++14	100 / 100	1935 ms	44652 KiB

cities

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <pair <int, int>> adj[N];

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

int ct[N];
int n,m,k;

int bit(int x) {
	return (1 << x);
}

void solve(int mask) {
	for (int i = 1; i <= n; i++)
	for (int s = mask; s > 0; s = (s - 1) & mask) 
		mini(dp[mask][i], dp[s][i] + dp[mask ^ s][i]);
	
	priority_queue <pair <long long, int>> heap;

	for (int i = 1; i <= n; i++)
		if (dp[mask][i] < ooo)
			heap.push(mp(-dp[mask][i], i));

	while (heap.size()) {
		int u = heap.top().se;
		long long cur = -heap.top().fi;
		heap.pop();
		if (cur != dp[mask][u])
			continue;

		for (pair <int, int> to : adj[u]) {
			int v = to.fi;
			int w = to.se;
			if (mini(dp[mask][v], dp[mask][u] + w))
				heap.push(mp(-dp[mask][v], v));
		}	
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	scanf("%d%d%d", &n, &k, &m);
	for (int i = 1; i <= k; i++)
		scanf("%d", &ct[i]);

	for (int i = 1; i <= m; i++) {
		int u,v,w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back(mp(v, w));
		adj[v].push_back(mp(u, w));
	}

	for (int mask = 0; mask < bit(k); mask++)
	for (int i = 1; i <= n; i++)
		dp[mask][i] = ooo;


	for (int i = 1; i <= k; i++)
		dp[bit(i - 1)][ct[i]] = 0;
	
	for (int mask = 0; mask < bit(k); mask++)
		solve(mask);

	long long ans = ooo;
	for (int i = 1; i <= n; i++)
		mini(ans, dp[bit(k) - 1][i]);

	printf("%ld", ans);
	return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:91:12: warning: format '%ld' expects argument of type 'long int', but argument 2 has type 'long long int' [-Wformat=]
   91 |  printf("%ld", ans);
      |          ~~^   ~~~
      |            |   |
      |            |   long long int
      |            long int
      |          %lld
cities.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d%d", &n, &k, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d", &ct[i]);
      |   ~~~~~^~~~~~~~~~~~~~
cities.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   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