oj.uz

Submission #531440

# Submission time Handle Problem Language Result Execution time Memory
531440 2022-02-28T17:05:42 Z Yazan_Alattar Cities (BOI16_cities) C++14
100 / 100
 2185 ms 48708 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 29880 KB Output is correct
2 Correct 528 ms 29400 KB Output is correct
3 Correct 286 ms 19896 KB Output is correct
4 Correct 68 ms 15216 KB Output is correct
5 Correct 300 ms 24552 KB Output is correct
6 Correct 65 ms 15136 KB Output is correct
7 Correct 4 ms 2892 KB Output is correct
8 Correct 4 ms 2840 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3020 KB Output is correct
2 Correct 6 ms 3044 KB Output is correct
3 Correct 6 ms 2892 KB Output is correct
4 Correct 4 ms 2892 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1079 ms 36124 KB Output is correct
2 Correct 931 ms 35588 KB Output is correct
3 Correct 580 ms 26108 KB Output is correct
4 Correct 549 ms 27364 KB Output is correct
5 Correct 151 ms 17612 KB Output is correct
6 Correct 73 ms 17468 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1998 ms 48676 KB Output is correct
2 Correct 2185 ms 48708 KB Output is correct
3 Correct 2173 ms 48044 KB Output is correct
4 Correct 1473 ms 38720 KB Output is correct
5 Correct 1238 ms 33444 KB Output is correct
6 Correct 303 ms 19068 KB Output is correct
7 Correct 94 ms 17468 KB Output is correct