oj.uz

Submission #64500

# Submission time Handle Problem Language Result Execution time Memory
64500 2018-08-04T16:32:50 Z TadijaSebez Cities (BOI16_cities) C++11
100 / 100
 5451 ms 64328 KB 
#include <stdio.h>
#include <set>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
const ll inf=1e18;
const int N=100050;
ll min(ll a, ll b){ return a>b?b:a;}
ll dp[N][1<<5];
vector<pair<int,int> > E[N];
//set<pair<ll,int> > ord;
priority_queue<pair<ll,int> > pq;
void Extend(int x, int n)
{
	int i;
	for(i=1;i<=n;i++) pq.push(mp(-dp[i][x],i));//ord.insert(mp(dp[i][x],i));
	while(pq.size())
	{
		//int u=ord.begin()->second;
		//ord.erase(ord.begin());
		int u=pq.top().second;
		ll h=-pq.top().first;
		pq.pop();
		if(h!=dp[u][x]) continue;
		for(i=0;i<E[u].size();i++)
		{
			int v=E[u][i].first;
			int w=E[u][i].second;
			if(dp[v][x]>dp[u][x]+w)
			{
				//ord.erase(mp(dp[v][x],v));
				dp[v][x]=dp[u][x]+w;
				pq.push(mp(-dp[v][x],v));
				//ord.insert(mp(dp[v][x],v));
			}
		}
	}
}
int count(int x){ int ret=0;while(x) ret+=x&1,x>>=1;return ret;}
int p[5];
int main()
{
	int n,k,m,i,j,u,v,w;
	scanf("%i %i %i",&n,&k,&m);
	for(i=0;i<k;i++) scanf("%i",&p[i]);
	for(i=1;i<=m;i++) scanf("%i %i %i",&u,&v,&w),E[u].pb(mp(v,w)),E[v].pb(mp(u,w));
	for(i=0;i<1<<k;i++) for(j=1;j<=n;j++) dp[j][i]=inf;
	for(i=0;i<k;i++) dp[p[i]][1<<i]=0;
	int mask;
	for(mask=1;mask<1<<k;mask++)
	{
		//printf("%i :D\n",mask);
		if(count(mask)>1)
		{
			for(j=(mask-1)&mask;j;j=(j-1)&mask)
			{
				int l=mask^j;
				//printf("%i %i\n",mask,j);
				for(i=1;i<=n;i++) dp[i][mask]=min(dp[i][mask],dp[i][j]+dp[i][l]);
			}
		}
		Extend(mask,n);
	}
	mask--;
	ll sol=inf;
	for(i=1;i<=n;i++) sol=min(sol,dp[i][mask]);
	printf("%lld\n",sol);
	return 0;
}

Compilation message

cities.cpp: In function 'void Extend(int, int)':
cities.cpp:28:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<E[u].size();i++)
           ~^~~~~~~~~~~~
cities.cpp: In function 'int main()':
cities.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&k,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
cities.cpp:48:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=0;i<k;i++) scanf("%i",&p[i]);
                   ~~~~~^~~~~~~~~~~~
cities.cpp:49:63: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=m;i++) scanf("%i %i %i",&u,&v,&w),E[u].pb(mp(v,w)),E[v].pb(mp(u,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 2776 KB Output is correct
3 Correct 4 ms 2776 KB Output is correct
4 Correct 6 ms 2800 KB Output is correct
5 Correct 4 ms 2872 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1177 ms 38508 KB Output is correct
2 Correct 1293 ms 38508 KB Output is correct
3 Correct 829 ms 38508 KB Output is correct
4 Correct 131 ms 38508 KB Output is correct
5 Correct 731 ms 38564 KB Output is correct
6 Correct 107 ms 38564 KB Output is correct
7 Correct 10 ms 38564 KB Output is correct
8 Correct 7 ms 38564 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 38564 KB Output is correct
2 Correct 12 ms 38564 KB Output is correct
3 Correct 11 ms 38564 KB Output is correct
4 Correct 10 ms 38564 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2584 ms 38564 KB Output is correct
2 Correct 2715 ms 42324 KB Output is correct
3 Correct 1818 ms 42324 KB Output is correct
4 Correct 1594 ms 42324 KB Output is correct
5 Correct 375 ms 42324 KB Output is correct
6 Correct 172 ms 42324 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5451 ms 56276 KB Output is correct
2 Correct 5058 ms 60624 KB Output is correct
3 Correct 5318 ms 64328 KB Output is correct
4 Correct 3849 ms 64328 KB Output is correct
5 Correct 3088 ms 64328 KB Output is correct
6 Correct 586 ms 64328 KB Output is correct
7 Correct 186 ms 64328 KB Output is correct