Submission #531440

#	Time	Username	Problem	Language	Result	Execution time	Memory
531440		Yazan_Alattar	Cities (BOI16_cities)	C++14	100 / 100	2185 ms	48708 KiB

cities

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

vector < pair <int,ll> > adj[M];
int n, k, m, city[10];
ll dp[70][M];

int main(){
	scanf("%d%d%d", &n, &k, &m);
	for(int i = 1; i <= k; ++i) scanf("%d", &city[i]);
	for(int i = 1; i <= m; ++i){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		adj[a].pb({b, c});
		adj[b].pb({a, c});
	}
	
	for(int mask = 0; mask < (1 << k); ++mask) for(int i = 1; i <= n; ++i) dp[mask][i] = inf;
	for(int i = 1; i <= k; ++i) dp[(1 << (i - 1))][city[i]] = 0;
	
	for(int mask = 1; mask < (1 << k); ++mask){
		priority_queue < pair <ll,int> > q;
		for(int i = 1; i <= n; ++i) if(dp[mask][i] != inf) q.push({-dp[mask][i], i});
		
		while(!q.empty()){
			int node = q.top().S;
			ll cost = -q.top().F;
			q.pop();
			if(cost != dp[mask][node]) continue;
			
			for(auto i : adj[node]) if(cost + i.S < dp[mask][i.F]){
				dp[mask][i.F] = cost + i.S;
				q.push({-cost -i.S, i.F});
			}
		}
		
		for(int mask2 = 1; mask2 < (1 << k); ++mask2) if((mask & mask2) == 0)
			for(int i = 1; i <= n; ++i)
				dp[(mask2 | mask)][i] = min(dp[(mask2 | mask)][i], dp[mask][i] + dp[mask2][i]);
	}
	
	ll ans = inf;
	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:22:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  scanf("%d%d%d", &n, &k, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:23:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  for(int i = 1; i <= k; ++i) scanf("%d", &city[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~~
cities.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d%d%d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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