oj.uz

Submission #45071

# Submission time Handle Problem Language Result Execution time Memory
45071 2018-04-11T06:41:35 Z nibnalin Cities (BOI16_cities) C++17
51 / 100
 4000 ms 56872 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;

typedef long long int lli;

const lli maxn = lli(1e5)+5, maxk = 6, inf = lli(1e17)+5;

lli n, D[maxk][maxn], dp[(1<<maxk)][maxn], A[maxk];
vector<pair<lli, lli>> graph[maxn];

void dijkstra(lli type, lli node)
{
	for(lli i = 0;i < n;i++) D[type][i] = inf;
	D[type][node] = 0;

	set<pair<lli, lli>> Q;
	Q.insert({D[type][node], node});

	while(!Q.empty())
	{
		pair<lli, lli> top = *Q.begin();
		Q.erase(Q.begin());

		for(auto it: graph[top.second])
		{
			if(D[type][it.first] > D[type][top.second]+it.second)
			{
				if(D[type][it.first] != inf) Q.erase({D[type][it.first], it.first});
				D[type][it.first] = D[type][top.second]+it.second;
				Q.insert({D[type][it.first], it.first});
			}
		}
	}
}

int main(void)
{
	lli k, m, u, v, w;
	scanf("%lld%lld%lld", &n, &k, &m);
	for(lli i = 0;i < k;i++)
	{
		scanf("%lld", &A[i]);
		A[i]--;
	}

	for(lli i = 0;i < m;i++)
	{
		scanf("%lld%lld%lld", &u, &v, &w);
		u--, v--;
		graph[u].push_back({v, w}), graph[v].push_back({u, w});
	}

	for(lli i = 0;i < k;i++) dijkstra(i, A[i]);

	for(lli mask = 1;mask < (1<<k);mask++)
	{
		set<pair<lli, lli>> Q;
		for(lli i = 0;i < n;i++)
		{
			dp[mask][i] = inf;
			for(lli j = 0;j < k;j++)
			{
				if((mask&(1<<j))) dp[mask][i] = min(dp[mask][i], dp[(mask^(1<<j))][i]+D[j][i]);
			}
			Q.insert({dp[mask][i], i});
		}

		while(!Q.empty())
		{
			pair<lli, lli> top = *Q.begin();
			Q.erase(Q.begin());

			for(auto it: graph[top.second])
			{
				if(dp[mask][it.first] > dp[mask][top.second]+it.second)
				{
					Q.erase({dp[mask][it.first], it.first});
					dp[mask][it.first] = dp[mask][top.second]+it.second;
					Q.insert({dp[mask][it.first], it.first});
				}
			}
		}
	}

	lli res = inf;
	for(lli 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:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &n, &k, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &A[i]);
   ~~~~~^~~~~~~~~~~~~~~
cities.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 4 ms 2796 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 4 ms 2988 KB Output is correct
5 Correct 4 ms 3024 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1895 ms 27056 KB Output is correct
2 Correct 1917 ms 30500 KB Output is correct
3 Correct 866 ms 30500 KB Output is correct
4 Correct 129 ms 30500 KB Output is correct
5 Correct 858 ms 37216 KB Output is correct
6 Correct 113 ms 37216 KB Output is correct
7 Correct 9 ms 37216 KB Output is correct
8 Correct 6 ms 37216 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 37216 KB Output is correct
2 Correct 13 ms 37216 KB Output is correct
3 Correct 9 ms 37216 KB Output is correct
4 Correct 9 ms 37216 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3888 ms 51928 KB Output is correct
2 Execution timed out 4022 ms 55420 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4045 ms 56872 KB Time limit exceeded
2 Halted 0 ms 0 KB -