oj.uz

Submission #410670

# Submission time Handle Problem Language Result Execution time Memory
410670 2021-05-23T10:02:42 Z antontsiorvas Cities (BOI16_cities) C++14
100 / 100
 2870 ms 46752 KB 
#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>
#define lli long long int
using namespace std;

int N, K, M, import[7], from, to;
lli weight, dp[33][100005];
vector< pair<int, lli> > data[100005];
bool visited[100005];
priority_queue< pair<lli, int> > pq; 
lli inf = 9000000000000000000;

int main(){
	scanf("%d%d%d",&N,&K,&M);
	for(int i=1; i<=K; i++) scanf("%d",&import[i]);
	for(int i=1; i<=M; i++){
		scanf("%d%d%lld",&from,&to,&weight);
		data[from].push_back(make_pair(to,weight));
		data[to].push_back(make_pair(from,weight));
	}
	
	int to = (1 << K);
	for(int i=0; i<to; i++){
		for(int j=1; j<=N; j++) dp[i][j] = inf;
	}
	for(int i=0; i<K; i++) dp[1 << i][import[i+1]] = 0;
	
	for(int i=1; i<to; i++){
		for(int j=1; j<=N; j++) visited[j] = false;
		for(int prev=0; prev<i; prev++){
			int b_or = (prev | i), b_xor = (prev ^ i);
			if(b_or != i || prev < b_xor) continue;
			for(int j=1; j<=N; j++){
				dp[i][j] = min(dp[i][j],dp[prev][j]+dp[b_xor][j]);
			}
		}
		
		for(int j=1; j<=N; j++){
			if(dp[i][j] != inf) pq.push(make_pair(-dp[i][j],j));
		}
		
		while(!pq.empty()){
			int city = pq.top().second;
			lli dpnum = -pq.top().first;
			pq.pop();
			visited[city] = true;
			int len = data[city].size();
			for(int j=0; j<len; j++){
				int next_city = data[city][j].first;
				lli cost = data[city][j].second;
				if(dpnum + cost < dp[i][next_city]){
					dp[i][next_city] = dpnum + cost;
					pq.push(make_pair(-dp[i][next_city],next_city));
				}
			}
		}
	}
	
	lli ans = inf;
	for(int i=1; i<=N; i++) ans = min(ans, dp[to-1][i]);
	printf("%lld",ans);
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  scanf("%d%d%d",&N,&K,&M);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
cities.cpp:18:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  for(int i=1; i<=K; i++) scanf("%d",&import[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~
cities.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%d%d%lld",&from,&to,&weight);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 27888 KB Output is correct
2 Correct 680 ms 26924 KB Output is correct
3 Correct 367 ms 18488 KB Output is correct
4 Correct 102 ms 15120 KB Output is correct
5 Correct 339 ms 24728 KB Output is correct
6 Correct 95 ms 15052 KB Output is correct
7 Correct 5 ms 2892 KB Output is correct
8 Correct 4 ms 2892 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1434 ms 34044 KB Output is correct
2 Correct 1353 ms 33064 KB Output is correct
3 Correct 794 ms 24760 KB Output is correct
4 Correct 779 ms 25824 KB Output is correct
5 Correct 224 ms 17392 KB Output is correct
6 Correct 119 ms 17636 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2618 ms 46752 KB Output is correct
2 Correct 2870 ms 46516 KB Output is correct
3 Correct 2632 ms 45708 KB Output is correct
4 Correct 1756 ms 37220 KB Output is correct
5 Correct 1452 ms 32192 KB Output is correct
6 Correct 342 ms 18732 KB Output is correct
7 Correct 147 ms 17608 KB Output is correct