Submission #2835141
Source Code Expand
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=17;
const int INF=0x3f3f3f3f;
ll n,m,conn[MAX][MAX],dist[MAX][MAX],dp[MAX][1<<MAX],visit[MAX][1<<MAX],calc[1<<MAX],trk[MAX],ans;
void calc_build(ll x,ll v,ll idx){
//printf("%lld %lld %lld\n",x,v,idx);
if(idx>=n) {
calc[x]=v;
return;
}
calc_build(x,v,idx+1);
trk[idx]=1;
for(ll i=0;i<idx;i++) if(trk[i]) v+=dist[i][idx];
calc_build(x+(1<<idx),v,idx+1);
trk[idx]=0;
}
ll dp_build(ll x,ll bit){
if(x==n-1) return dp[x][bit]=calc[bit];
if(visit[x][bit]==0){
visit[x][bit]=1;
for(ll i=0;i<n;i++) if(((1<<i)&bit)&&conn[i][x]){
ll cmp[MAX],cmp_cnt=0;
for(ll j=0;j<n-1;j++) if(((1<<j)&bit)&&i!=j&&x!=j) cmp[cmp_cnt++]=j;
for(ll j=0;j<(1<<(cmp_cnt));j++){
ll g1=1<<x,g2;
for(ll k=0;k<cmp_cnt;k++) if((1<<k)&j) g1+=(1<<cmp[k]);
g2=bit-g1;
dp[x][bit]=max(dp[x][bit],calc[g1]+dp_build(i,g2)+dist[x][i]);
}
}
}
return dp[x][bit];
}
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=0;i<m;i++){
ll t1,t2,t;
scanf("%lld%lld%lld",&t1,&t2,&t);
t1--,t2--;
conn[t1][t2]=1,dist[t1][t2]=t;
conn[t2][t1]=1,dist[t2][t1]=t;
ans+=t;
}
calc_build(0,0,0);
printf("%lld\n",ans-dp_build(0,(1<<n)-1));
}
Submission Info
Submission Time
2018-07-13 21:24:17+0900
Task
F - Mole and Abandoned Mine
User
x0000ai
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1558 Byte
Status
WA
Exec Time
1162 ms
Memory
31360 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:42:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&n,&m);
^
./Main.cpp:45:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&t1,&t2,&t);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 900
Status
Set Name
Test Cases
Sample
00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All
00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt
Case Name
Status
Exec Time
Memory
00_example_01.txt
AC
2 ms
6400 KB
00_example_02.txt
AC
2 ms
2304 KB
00_example_03.txt
AC
93 ms
31232 KB
01.txt
AC
863 ms
31232 KB
02.txt
AC
9 ms
22784 KB
03.txt
AC
2 ms
2304 KB
04.txt
AC
3 ms
10496 KB
05.txt
AC
2 ms
2304 KB
06.txt
AC
5 ms
18688 KB
07.txt
AC
5 ms
18688 KB
08.txt
AC
95 ms
27008 KB
09.txt
AC
5 ms
18688 KB
10.txt
AC
2 ms
6400 KB
11.txt
AC
866 ms
31232 KB
12.txt
AC
93 ms
31232 KB
13.txt
AC
849 ms
31232 KB
14.txt
AC
486 ms
31232 KB
15.txt
AC
869 ms
31360 KB
16.txt
AC
823 ms
31232 KB
17.txt
AC
709 ms
31232 KB
18.txt
WA
102 ms
29184 KB
19.txt
AC
346 ms
31232 KB
20.txt
AC
1031 ms
31232 KB
21.txt
AC
1161 ms
31232 KB
22.txt
AC
1161 ms
31360 KB
23.txt
AC
1161 ms
31360 KB
24.txt
AC
1162 ms
31232 KB
25.txt
AC
1161 ms
31232 KB