oj.uz

Submission #64499

# Submission time Handle Problem Language Result Execution time Memory
64499 2018-08-04T16:29:49 Z TadijaSebez Cities (BOI16_cities) C++11
51 / 100
 6000 ms 60684 KB 
#include <stdio.h>
#include <set>
#include <vector>
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;
void Extend(int x, int n)
{
	int i;
	for(i=1;i<=n;i++) ord.insert(mp(dp[i][x],i));
	while(ord.size())
	{
		int u=ord.begin()->second;
		ord.erase(ord.begin());
		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;
				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:22: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:40: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:41: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:42: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 5 ms 2680 KB Output is correct
2 Correct 4 ms 2856 KB Output is correct
3 Correct 7 ms 2856 KB Output is correct
4 Correct 5 ms 2876 KB Output is correct
5 Correct 5 ms 2876 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2885 ms 42192 KB Output is correct
2 Correct 2963 ms 46220 KB Output is correct
3 Correct 1378 ms 46220 KB Output is correct
4 Correct 124 ms 46220 KB Output is correct
5 Correct 1366 ms 56508 KB Output is correct
6 Correct 147 ms 56508 KB Output is correct
7 Correct 11 ms 56508 KB Output is correct
8 Correct 10 ms 56508 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 56508 KB Output is correct
2 Correct 20 ms 56508 KB Output is correct
3 Correct 15 ms 56508 KB Output is correct
4 Correct 14 ms 56508 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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