oj.uz

Submission #866204

# Submission time Handle Problem Language Result Execution time Memory
866204 2023-10-25T15:23:59 Z alwaystle Cities (BOI16_cities) C++17
0 / 100
 5 ms 27740 KB 
#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);
	#ifndef ONLINE_JUDGE
	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

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) {
      |               ~~^~~~~~~~~~~~~~~
cities.cpp:24:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:24:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
      |                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 27740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 27740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 27740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 27736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 27736 KB Output isn't correct
2 Halted 0 ms 0 KB -