2014
11-05

# A sample Hamilton path

Give you a Graph,you have to start at the city with ID zero.

The first line is n(1<=n<=21) m(0<=m<=3)
The next n line show you the graph, each line has n integers.
The jth integers means the length to city j.if the number is -1 means there is no way. If i==j the number must be -1.You can assume that the length will not larger than 10000
Next m lines,each line has two integers a,b (0<=a,b<n) means the path must visit city a first.
The input end with EOF.

The first line is n(1<=n<=21) m(0<=m<=3)
The next n line show you the graph, each line has n integers.
The jth integers means the length to city j.if the number is -1 means there is no way. If i==j the number must be -1.You can assume that the length will not larger than 10000
Next m lines,each line has two integers a,b (0<=a,b<n) means the path must visit city a first.
The input end with EOF.

3 0
-1 2 4
-1 -1 2
1 3 -1
4 3
-1 2 -1 1
2 -1 2 1
4 3 -1 1
3 2 3 -1
1 3
0 1
2 3

4
5

HintI think that all of you know that a!=b and b!=0    =。= 

#include<stdio.h>
#include<string.h>
const int INFI=999999999;

int pre[30][10],pow[30];
int map[30][30];
int f[1<<20][21];
int n,m;

bool check(int s,int v)
{
for (int i=1;i<=pre[v][0];i++)
if ( (s&pow[pre[v][i]])==0 )
return 0;
return 1;
}

int main()
{
int a,b;

for (int i=0;i<22;i++) pow[i] = 1<<i;

while ( scanf("%d%d",&n,&m)!=EOF )
{
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
scanf("%d",&map[i][j]);

memset(pre,0,sizeof(pre));
for (int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
pre[b][ ++pre[b][0] ]=a;
}
int maxs = (1<<n)-1;
for (int s=0;s<=maxs;s++)
for (int i=0;i<n;i++)
f[s][i]=INFI;

f[1][0]=0;

for (int s=1;s<=maxs;s++)
for (int i=0;i<n;i++)
if ( (s & pow[i])>0 && f[s][i]<INFI )
{
for (int j=1;j<n;j++)
if ( map[i][j]!=-1 && (s&pow[j])==0 && check(s,j) )
{
if ( f[s][i]+map[i][j] < f[ s+pow[j] ][j] )
{
f[s+pow[j]][j] = f[s][i]+map[i][j];
//printf("updata[%d][%d] is %d\n",s+pow[j],j,f[s+pow[j]][j]);
}
}
//printf("f[%d][%d] is %d\n",s,i,f[s][i]);
}

int ans=INFI;
for (int i=0;i<n;i++)
if ( f[maxs][i]<ans )
ans=f[maxs][i];
if ( ans==INFI )
printf("-1\n");
else
printf("%d\n",ans);
}
}

1. 呃看完了，看到最后的一句话，我才明白，你是个科学狂热分子，我不否认科学的创造性和必须性。但我不认为科学便是一切！科学也有错。哼，不需要解释！

2. 呃看完了，看到最后的一句话，我才明白，你是个科学狂热分子，我不否认科学的创造性和必须性。但我不认为科学便是一切！科学也有错。哼，不需要解释！

3. 呃看完了，看到最后的一句话，我才明白，你是个科学狂热分子，我不否认科学的创造性和必须性。但我不认为科学便是一切！科学也有错。哼，不需要解释！

4. 呃看完了，看到最后的一句话，我才明白，你是个科学狂热分子，我不否认科学的创造性和必须性。但我不认为科学便是一切！科学也有错。哼，不需要解释！

5. 呃看完了，看到最后的一句话，我才明白，你是个科学狂热分子，我不否认科学的创造性和必须性。但我不认为科学便是一切！科学也有错。哼，不需要解释！

6. 呃看完了，看到最后的一句话，我才明白，你是个科学狂热分子，我不否认科学的创造性和必须性。但我不认为科学便是一切！科学也有错。哼，不需要解释！

7. 呃看完了，看到最后的一句话，我才明白，你是个科学狂热分子，我不否认科学的创造性和必须性。但我不认为科学便是一切！科学也有错。哼，不需要解释！

8. 呃看完了，看到最后的一句话，我才明白，你是个科学狂热分子，我不否认科学的创造性和必须性。但我不认为科学便是一切！科学也有错。哼，不需要解释！

9. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count