Submission #866205

#	Time	Username	Problem	Language	Result	Execution time	Memory
866205		alwaystle	Cities (BOI16_cities)	C++17	100 / 100	1772 ms	47924 KiB

cities

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define file "test"
#define vi vector
#define sz(_v) _v.begin(), _v.end()
#define mask(_x) (1ll << (_x))
#define mp make_pair
#define fi first
#define se second
typedef pair<ll,int> pa;
 
const ll inf = ll(1e16) + 1;
const int N = 1e5 + 5;
int n, m, k, x, y, i, a[6], j, l, p;
vi<pa> adj[N];
ll z, dp[1 << 5][N], o = inf;
bool dd[N];
priority_queue<pa> pq;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	#ifdef umf
	freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
	// freopen("debug.txt","w",stderr);
	#endif
 
	cin >> n >> k >> m;
	for(i = 1; i <= k; ++i) cin >> a[i];
	while(m--) {
		cin >> x >> y >> z;
		adj[x].push_back(mp(z,y));
		adj[y].push_back(mp(z,x));
	}
	memset(dp,63,sizeof(dp));
	for(i = 0; i < k; ++i) dp[mask(i)][a[i + 1]] = 0;
	for(i = 1; i < mask(k); ++i) {
		for(j = 0; j < i; ++j)
			if((i | j) == i) {
				l = i ^ j;
				if(l < j) for(p = 1; p <= n; ++p) dp[i][p] = min(dp[i][p],dp[j][p] + dp[l][p]);
			}
		memset(dd,false,sizeof(dd));
		for(j = 1; j <= n; ++j)
			if(dp[i][j] < inf) pq.push(mp(-dp[i][j],j));
		while(!pq.empty()) {
			x = pq.top().se;
			pq.pop();
			dd[x] = true;
			for(j = 0; j < adj[x].size(); ++j) {
				y = adj[x][j].se;
				z = adj[x][j].fi;
				if(!dd[y] && dp[i][x] + z < dp[i][y]) {
					dp[i][y] = dp[i][x] + z;
					pq.push(mp(-dp[i][y],y));
				}
			}
			while(!pq.empty() && dd[pq.top().se]) pq.pop();
		}
	}
	x = mask(k) - 1;
	for(i = 1; i <= n; ++i) o = min(o,dp[x][i]);
	cout << o;
 
	return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for(j = 0; j < adj[x].size(); ++j) {
      |               ~~^~~~~~~~~~~~~~~

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