城市地图

/*《啊哈！算法》P152/140*/ 
#include<stdio.h>
//假设99999999为正无穷 
int min = 99999999, book[100], n, e[100][100];

//cur当前城市编号，dis是当前已走过的路程
void dfs(int cur, int dis) {
	int j;
	//如果当前走过的路程已经大于之前找到的最短路，则没有必要往下尝试，立即返回
	if(dis > min) {
		return;
	} 
	//判断是否到达目标城市
	if(cur == n-1) {
		if(dis < min) {
			min = dis; //更新最小值 
		}
		return; 
	} 
	//依次尝试这n个城市 
	for(j = 0; j < n; j++) {
		//判断两者之间是否有路，并判断j是否已经走过
		if(e[cur][j] != 0 && book[j] == 0) {
			book[j] = 1; //标记城市j已经在路径中
			dfs(j, dis+e[cur][j]);
			book[j] = 0; //探索完成后取消对城市j的标记 
		} 
	}
	
	return; 
} 

int main(void) {
	int i, j;
	//录入信息 
	scanf("%d", &n);
	for(i = 0; i < n; i++) {
		for(j = 0; j < n; j++) {
			scanf("%d", &e[i][j]);
		}
	}
	
	book[0] = 1;
	dfs(0, 0);
	printf("%d", min);
	
	return 0;
}