hdu3001 Travelling

hdu3001 Travelling

Problem Description After coding so many days,Mr Acmer wants to have a good rest.So travelling is the best choice!He has decided to visit n cities(he insists on seeing all the cities!And he does not mind which city being his start station because superman can bring him to any city at first but only once.), and of course there are m roads here,following a fee as usual.But Mr Acmer gets bored so easily that he doesn't want to visit a city more than twice!And he is so mean that he wants to minimize the total fee!He is lazy you see.So he turns to you for help.
Input There are several test cases,the first line is two intergers n(1<=n<=10) and m,which means he needs to visit n cities and there are m roads he can choose,then m lines follow,each line will include three intergers a,b and c(1<=a,b<=n),means there is a road between a and b and the cost is of course c.Input to the End Of File.
Output Output the minimum fee that he should pay,or -1 if he can't find such a route.
Sample Input

2 1
1 2 100
3 2
1 2 40
2 3 50
3 3
1 2 3
1 3 4
2 3 10

Sample Output

100
90
7 

 

看了別人的思路，自己寫出來了：）。這題和poj3311差不多，但是不能用floyd處理，因為它有訪問次數限制，最多相同的地方訪問兩次，至少一次，所以為了存儲狀態，我們可以用三進制表示，1代表訪問一次，2代表訪問2次。動態轉移方程也和之前的差不多，為dp[s][i]=min(dp[s][i],dp[s-san[i-1]][j]+dis[j][i])。最後的結論要在訪問過程中產生，如果當前所枚舉的狀態符合用三進制表示後每一位的數都大於0，那麼就表示都訪問到了，就可以和所求的結果ans比，如果比ans小就更新。

 

#include
#include
#define inf 88888888
int dis[15][15],dp[200000][15],wei[15],num,t;
int san[15]={1,3,9,27,81,243,729,2187,6561,19683,59049,177147};
int min(int a,int b){
	return a0){
		if(x%3>0)num++;
		wei[++t]=x%3;
		x=x/3;
	}
}

int main()
{
	int n,m,i,j,a,b,c,s,ans;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				dis[i][j]=inf;
			}
		}
		for(i=1;i<=m;i++){
			scanf("%d%d%d",&a,&b,&c);
		    if(dis[a][b]>c)dis[a][b]=dis[b][a]=c;
		}
		ans=inf;
		for(s=1;s=i && wei[t]>0){
					if(s==san[i-1]){
						dp[s][i]=0;
					}
					else{
						for(j=1;j<=n;j++){
							if(j!=i && wei[j]>0){
								dp[s][i]=min(dp[s][i],dp[s-san[i-1]][j]+dis[j][i]);
								if(num==n){
									ans=min(ans,dp[s][i]);
								}
							}
						}
					}
				}
			}
			if(ans==0)break;
		}
		if(ans==inf)printf("-1\n");
		else printf("%d\n",ans);
	}
}