- #include
- #include
- #include
- using namespace std;
- const intmaxn=20;
- intn,mp[maxn][maxn],f[maxn][70010];
- int main()
- {
- scanf("%d",&n);n++;
- int x;
- for(inti=1;i<=n;i++)
- {
- for(intj=1;j<=n;j++)
- {
- scanf("%d",&x);
- mp[i][j]=x;
- }
- }
- for(inti=1;i<=n;i++)mp[i][i]=0;
- for(intk=1;k<=n;k++)
- for(inti=1;i<=n;i++)
- for(intj=1;j<=n;j++)
- mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
- memset(f,0x3f,sizeof(f));
- f[1][0]=0;
- for(intk=1;k<=(1<1;k++)
- for(inti=1;i<=n;i++)
- for(intj=1;j<=n;j++)
- if((1<<(i-1))&k)f[i][k]=min(f[i][k],f[j][k-(1<<(i-1))]+mp[j][i]);
- printf("%d",f[1][(1<1]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1969499.html