Submission #873600


Source Code Expand

Copy
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
int p[21][2];

int g[21][21];
int dame[1<<20];
int dp[1<<20][20][2];
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	for(int i=0;i<a;i++){
		scanf("%d%d",&p[i][0],&p[i][1]);
	}
	for(int i=0;i<a;i++)g[i][i]=1;
	for(int i=0;i<b;i++){
		int s,t;scanf("%d%d",&s,&t);
		s--;t--;
		g[s][t]=1;
	}
	for(int k=0;k<a;k++)for(int i=0;i<a;i++)for(int j=0;j<a;j++)
		g[i][j]|=(g[i][k]&g[k][j]);

	for(int i=0;i<(1<<a);i++){
		for(int j=0;j<a;j++){
			if(i&(1<<j))continue;
			for(int k=0;k<a;k++)if(j!=k)dame[i]|=(g[j][k]<<k);
		}
		dame[i]|=i;
	//	printf("%d: %d\n",i,dame[i]);
	}
	for(int i=0;i<(1<<a);i++)for(int j=0;j<a;j++)for(int k=0;k<2;k++)
		dp[i][j][k]=999999999;
	dp[0][0][0]=dp[0][0][1]=0;
	for(int i=0;i<(1<<a);i++){
		for(int j=0;j<a;j++){
			for(int k=0;k<2;k++){
				if(dp[i][j][k]>99999999)continue;
			//	printf("%d %d %d: %d\n",i,j,k,dp[i][j][k]);
				if(j<a-1)dp[i][j+1][!k]=min(dp[i][j+1][!k],dp[i][j][k]+(c*j+d));
				for(int l=0;l<a;l++){
					if(dame[i]&(1<<l))continue;
					dp[i+(1<<l)][j][k]=min(dp[i+(1<<l)][j][k],dp[i][j][k]+p[l][k]);
				}
			}
		}
	}
	int ret=999999999;
	for(int i=0;i<a;i++){
		for(int j=0;j<2;j++)ret=min(ret,dp[(1<<a)-1][i][j]);
	}
	printf("%d\n",ret);
}

Submission Info

Submission Time
Task D - 右往左往
User tozangezan
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1352 Byte
Status AC
Exec Time 2626 ms
Memory 168192 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:13:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&a,&b,&c,&d);
                               ^
./Main.cpp:15:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p[i][0],&p[i][1]);
                                  ^
./Main.cpp:19:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int s,t;scanf("%d%d",&s,&t);
                              ^

Judge Result

Set Name All
Score / Max Score 700 / 700
Status
AC × 30
Set Name Test Cases
All 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 10_manual_01, 10_manual_02, 20_v20_001, 20_v20_002, 20_v20_003, 20_v20_004, 20_v20_005, 20_v20_006, 20_v20_007, 20_v20_008, 20_v20_009, 20_v20_010, 20_v20_011, 20_v20_012, 20_v20_013, 20_v20_014, 30_random_01, 30_random_02, 30_random_03, 30_random_04, 30_random_05, 30_random_06, 40_random_01, 40_random_02, 50_maxmove_00, 50_maxmove_01
Case Name Status Exec Time Memory
00_sample_01 AC 2 ms 128 KB
00_sample_02 AC 2 ms 128 KB
00_sample_03 AC 2 ms 128 KB
00_sample_04 AC 2 ms 128 KB
10_manual_01 AC 2 ms 128 KB
10_manual_02 AC 2 ms 128 KB
20_v20_001 AC 2565 ms 168064 KB
20_v20_002 AC 2586 ms 168064 KB
20_v20_003 AC 2558 ms 168064 KB
20_v20_004 AC 2626 ms 168064 KB
20_v20_005 AC 835 ms 168064 KB
20_v20_006 AC 834 ms 168064 KB
20_v20_007 AC 831 ms 168064 KB
20_v20_008 AC 831 ms 168064 KB
20_v20_009 AC 841 ms 168192 KB
20_v20_010 AC 828 ms 168064 KB
20_v20_011 AC 830 ms 168064 KB
20_v20_012 AC 829 ms 168064 KB
20_v20_013 AC 834 ms 168064 KB
20_v20_014 AC 827 ms 168064 KB
30_random_01 AC 827 ms 168064 KB
30_random_02 AC 829 ms 168064 KB
30_random_03 AC 832 ms 168064 KB
30_random_04 AC 829 ms 168064 KB
30_random_05 AC 829 ms 168064 KB
30_random_06 AC 830 ms 168064 KB
40_random_01 AC 831 ms 168064 KB
40_random_02 AC 835 ms 168064 KB
50_maxmove_00 AC 830 ms 168064 KB
50_maxmove_01 AC 830 ms 168064 KB