Submission #64500

#	Time	Username	Problem	Language	Result	Execution time	Memory
64500		TadijaSebez	Cities (BOI16_cities)	C++11	100 / 100	5451 ms	64328 KiB

cities

#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 (stderr)

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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26