pku 3394 dfs+剪枝.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

//PKU 3394? 搜索
#define NMAX 105
#define INFI 99999
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back

int cost[NMAX][NMAX];
bool visited[NMAX];
int totle,begin,end;//中间点总数、起始点、终止点
int ans;
int plu[NMAX];
typedef struct oopnode
{
	vector <int> next;
}oopnode;

oopnode node[NMAX];

void visit(int now,int count,int rout)
{
//	printf("now=%d\n",now);
	visited[now]=true;
	vector <int>::iterator p;
	if(count==totle)
	{
		if(cost[now][end]!=0 && ans>rout+cost[now][end])//注意这个剪枝
		   	ans=rout+cost[now][end];
		else return;
	}
	for(p=node[now].next.begin();p!=node[now].next.end();p++)
	{
		if(visited[*p]==false && rout+cost[now][*p]<ans)//注意这个剪枝
		{
			visit(*p,count+1,rout+cost[now][*p]);
			visited[*p]=false;
		}
	}
}

void init(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
		{
			if(cost[i][j]!=0) node[i].next.PB(j);
		}
	}
}

void solve(int num)
{
	vector <int>::iterator p;
	int min;
	ans=INFI;
//	ans.clear();
//	init(num);
	visit(begin,0,0);
	if(ans==INFI) printf("0\n");
	else printf("%d\n",ans);
//	min=INFI;
//	if(ans.empty()==true) printf("0\n");
//	else{
//	for(p=ans.begin();p!=ans.end();p++)
//	{
//		printf("*p=%d\n",*p);
//		if(min>*p) min=*p;
//	}
//	printf("%d\n",min);
//	}
}

int main()
{
	int i,j,num,qnum,t,k;
	char mm[NMAX];
	scanf("%d %d",&num,&qnum);
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			scanf("%d",&cost[i][j]);
	}
	init(num);
	cin.ignore();
	for(i=1;i<=qnum;i++)
	{
		cin.getline(mm,104);
//		printf("mm=%s\n",mm);
			k=0;
			for(j=0;mm[j]!='\0';j++)
			{
				t=0;
				while(mm[j]!=' ' && mm[j]!='\0')
				{
					t=t*10+mm[j]-'0';
					j++;
				}
				plu[++k]=t;
//				printf("t=%d\n",t);
				if(mm[j]=='\0') j--;
			}
			begin=plu[1];
			end=plu[k];
			totle=k-2;
//			printf("begin=%d end=%d\n",begin,end);
//			printf("\n");
//			for(j=1;j<=k;j++) printf("(%d)",plu[j]);
//			cout<<endl;
			for(j=1;j<=num;j++) visited[j]=true;
			for(j=1;j<=k-1;j++) visited[plu[j]]=false; 
			solve(num);
	}
	return 0;
}