深搜加记忆化搜索全WA求调,注释清晰
查看原帖
深搜加记忆化搜索全WA求调,注释清晰
1379306
Furinaaaa楼主2024/7/2 17:00

请各路大佬看看,哪里出了问题?谢谢

#define _CRT_SECURE_NO_WARNINGS


#include <iostream>
#include <limits.h>

using namespace std;


int n;

//记录村庄之间距离
//  dis[start][to]
int dis[30][30];

//记录最小解
//	fmin[start][num]
int fmin1[30][30];

//记录每个节点有没有访问过,初始值为0,访问后为1
int visited[30];

//比较大小
int mymin(int a, int b)
{
	if (a > b)
	{
		return b;
	}
	return a;
}
//深搜
//返回已经访问了num个村庄时,从start开始遍历到1的最小距离
int dfs(int start, int num)
{
	//出口
	if ( num == n - 1 ) 
	{
		return dis[start][1] ;
	}
	//其他情况

	//遍历所有子节点
	for (int i = 2; i <= n; i++)
	{
		//所有不是他本身的点
		if (i == start)
		{
			continue;
		}
		//目的地已访问,跳过
		if (visited[i] )
		{
			continue;
		}
		//访问
		visited[i] = 1;
		//fmin1[start][num] = mymin(fmin1[start][num], dfs(i, num + 1) + dis[start][i]) ; 
		return (fmin1[start][num] = mymin(fmin1[start][num], dfs(i, num + 1) + dis[start][i]));
		//回溯
		visited[i] = 0;

	}
}

int main()
{
	//freopen ( "P1171_1.in" , "r" , stdin ) ; 
	
	scanf("%d", &n);
	//输入数据
	for (int i = 1; i <= n; i++)
	{
		for (int u = 1; u <= n; u++)
		{
			scanf ("%d" , &dis[i][u]) ;  
		}
		

	}
	//freopen("P1171_1.out", "r", stdin);
	//int ans  ; 
	//cin >> ans ; 
	//初始化
	for (int i = 0; i <= 25; i++)
	{
		visited[i] = 0 ; 
		for (int u = 0; u <= 25; u++)
		{
			fmin1[i][u] = INT_MAX;
		}
	}
	
	visited[1] = 1;
	dfs ( 1 , 1 ) ;
	cout << fmin1[1][1] << endl ; 
	//cout << "------\n" ; 
	//cout << ans ; 




	return 0;



}
2024/7/2 17:00
加载中...