oj.uz

Submission #45084

# Submission time Handle Problem Language Result Execution time Memory
45084 2018-04-11T07:17:17 Z nibnalin Cities (BOI16_cities) C++17
100 / 100
 3924 ms 45124 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>
using namespace std;
 
typedef long long int lli;
 
const int maxn = lli(1e5)+5, maxk = 6;
const lli inf = lli(1e17)+5;
 
int n, A[maxk];
lli dp[(1<<maxk)][maxn];
vector<pair<int, int>> graph[maxn];

int main(void)
{
	int k, m, u, v, w;
	scanf("%d%d%d", &n, &k, &m);
	for(int i = 0;i < k;i++)
	{
		scanf("%d", &A[i]);
		A[i]--;
	}
 
	for(int i = 0;i < m;i++)
	{
		scanf("%d%d%d", &u, &v, &w);
		u--, v--;
		graph[u].push_back({v, w}), graph[v].push_back({u, w});
	}
 
	for(int i = 0;i < (1<<k);i++)
	{
		for(int j = 0;j < n;j++) dp[i][j] = inf;
	}
	for(int i = 0;i < k;i++) dp[(1<<i)][A[i]] = 0;
 
 
	for(int mask = 1;mask < (1<<k);mask++)
	{
		priority_queue<pair<lli, int>> Q;
		for(int i = 0;i < n;i++)
		{
			for(int j = 0;j < k;j++)
			{
				if((mask&(1<<j))) dp[mask][i] = min(dp[mask][i], dp[(mask^(1<<j))][i]+dp[(1<<j)][i]);
			}
			Q.push({-dp[mask][i], i});
		}
 
		while(!Q.empty())
		{
			pair<lli, int> top = Q.top();
			Q.pop();
 
			for(auto it: graph[top.second])
			{
				if(dp[mask][it.first] > dp[mask][top.second]+it.second)
				{
					dp[mask][it.first] = dp[mask][top.second]+it.second;
					Q.push({-dp[mask][it.first], it.first});
				}
			}
		}
	}
 
	lli res = inf;
	for(int i = 0;i < n;i++) res = min(res, dp[(1<<k)-1][i]);
	printf("%lld\n", res);
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
   ~~~~~^~~~~~~~~~~~~
cities.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2840 KB Output is correct
3 Correct 4 ms 2840 KB Output is correct
4 Correct 4 ms 2848 KB Output is correct
5 Correct 4 ms 2900 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 988 ms 21912 KB Output is correct
2 Correct 944 ms 21940 KB Output is correct
3 Correct 675 ms 21940 KB Output is correct
4 Correct 121 ms 21940 KB Output is correct
5 Correct 537 ms 21940 KB Output is correct
6 Correct 109 ms 21940 KB Output is correct
7 Correct 7 ms 21940 KB Output is correct
8 Correct 6 ms 21940 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21940 KB Output is correct
2 Correct 13 ms 21940 KB Output is correct
3 Correct 8 ms 21940 KB Output is correct
4 Correct 8 ms 21940 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1867 ms 28276 KB Output is correct
2 Correct 1784 ms 28412 KB Output is correct
3 Correct 1288 ms 28412 KB Output is correct
4 Correct 1066 ms 28412 KB Output is correct
5 Correct 296 ms 28412 KB Output is correct
6 Correct 129 ms 28412 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3662 ms 41092 KB Output is correct
2 Correct 3924 ms 41092 KB Output is correct
3 Correct 3835 ms 45124 KB Output is correct
4 Correct 2535 ms 45124 KB Output is correct
5 Correct 2017 ms 45124 KB Output is correct
6 Correct 428 ms 45124 KB Output is correct
7 Correct 156 ms 45124 KB Output is correct