hdu1572 水搜索

题意:

中文的不解释;

思路:

其实就是一个水的搜索,直接搜索不会超时,还有别跑最短路了,题目没要求跑最短路,别读错题,刚开始自己嘚嗖的跑了一边最短路 wa了 ,正好最近看了STL的全排列就写下吧,省着忘了,反正没有剪枝的深搜也是全排列的枚举..

#include<stdio.h>

#include<algorithm>

#define N 30 + 5

#define inf 1000000000

using namespace std;

int main ()

{
int map[N][N];
int num[10];
int i ,j ,k ,n ,nn ,ans;
while(scanf("%d" ,&n) && n)
{
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
{
scanf("%d" ,&map[i][j]);
}
scanf("%d" ,&nn);
for(i = 1 ;i <= nn ;i ++)
{
scanf("%d" ,&num[i]);
num[i] ++;
}
int c = 1;
for(i = 1 ;i <= nn ;i ++)
c *= i;
ans = inf;
int temp = map[1][num[1]];
for(i = 2 ;i <= nn ;i ++)
temp += map[num[i - 1]][num[i]];
if(ans > temp)
ans = temp;

while(--c)
{
next_permutation(num + 1 ,num + nn + 1);
temp = map[1][num[1]];
for(i = 2 ;i <= nn ;i ++)
temp += map[num[i - 1]][num[i]];
if(ans > temp)
ans = temp;
}
printf("%d\n" ,ans);
}
return 0;

}

巴特西

hdu1572 水搜索

最新文章

热门文章