POJ3311 Hie with the Pie 狀壓DP

POJ3311 Hie with the Pie 狀壓DP

今天好不容易切了兩道這樣的題目，第一道就不提了，完全是題目有特殊情況沒判，基本上是入門型的了，這道還不錯的，而且有個博客寫的特別的好，

http://www.tuicool.com/articles/aUnAru

轉一下他的狀態方程：

記dp(v, S)為從v點出發，遍歷S集合中的每一個點後，回到出發點（0點）的最短距離。遞推表達式的推導如下：

如果 S 為空集，即沒有需要遍歷的結點了。此時可以直接從v點回到0點，則dp(v,S)=sp[v][0] //sp[v][0] 是v點到0點的最短路徑距離

如果 S 不為空集，則 dp(v,S)=min{ sp[v][u] + dp(v,S-{u}) }//sp[v][u] 是v點到u點的最短路徑距離

這個狀態方程描述的就很好了，就算自己沒推出來，看了這個也還有自己去想的空間，化抽象為具體嘛，哈哈

int n;

int mp[10 + 5][10 + 5];

int dis[10 + 5][10 + 5];

int dp[1<<10][10 + 5];

void init() {
	memset(mp,0,sizeof(mp));
	memset(dis,0,sizeof(dis));
}

bool input() {
	while(scanf("%d",&n),n) {
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++) {
				scanf("%d",&mp[i][j]);
				dis[i][j] = mp[i][j];
			}
		return false;
	}
	return true;
}

void folyd() {
	for ( int i = 0; i <= n; ++i ) {
		for ( int j = 0; j <= n; ++j ) {
			for ( int k = 0; k <= n; ++k ) {
				if ( dis[i][k] + dis[k][j] < dis[i][j] ) 
					dis[i][j] = dis[i][k] + dis[k][j];
			}
		}
	}
}

void cal() {
	folyd();
	for(int i=1;i<=((1<