1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
|
#include<algorithm> #define LL long long using namespace std; const int N=22,INF=1<<20; int d[N][N],dp[N][1<<N],w[N],rec[1<<N],c[N],n,m,sum; inline int () { register int x=0,t=1; register char ch=getchar(); while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if (ch=='-') t=-1,ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t; } void floyd() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) if (i!=k) for(int j=1;j<=n;j++) if (k!=j&&i!=j) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } int main() { int T=read(); while (T--) { n=read(),m=read(),sum=0; for(int i=1;i<=n;i++) w[i]=read(),c[i]=read(); for(int i=1;i<=n;i++) sum+=w[i]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if (i!=j) d[i][j]=INF; for(int i=1;i<=m;i++) { int u=read(),v=read(); d[u][v]=d[v][u]=min(d[u][v],read()); } for(int i=1;i<=n;i++) for(int s=0;s<(1<<n);s++) dp[i][s]=INF; for(int s=0;s<(1<<n);s++) rec[s]=0; for(int s=0;s<(1<<n);s++) for(int i=1;i<=n;i++) if ((s>>(i-1))&1) rec[s]+=c[i]; floyd(),dp[1][1]=0; for(int s=0;s<(1<<n);s++) for(int i=1;i<=n;i++) if ((s>>(i-1))&1&&dp[i][s]<sum) for(int j=1;j<=n;j++) if (!((s>>(j-1))&1)) dp[j][s|(1<<(j-1))]=min(dp[j][s|(1<<(j-1))],dp[i][s]+rec[(1<<n)-1-s]*d[i][j]); int ans=-INF; for(int i=1;i<=n;i++) ans=max(ans,sum-dp[i][(1<<n)-1]); printf("%lldn",ans); } return 0; }
|
近期评论