3033221_ac_30ms_152k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n, lim;

struct node
{
	int b, c;
	int p, r;
};

vector <node> tree[10];
int visited[10], ans;


void dfs(int v)
{
	int i;
	node t;

	visited[v] = 1;
	for(i = 0; i < tree[v].size(); i++)
	{
		t = tree[v][i];
		if(!visited[t.b])
		{
			lim += t.r;
			dfs(t.b);
		}
	}
}

void Dfs(int v,int fee)
{
	node t;

	visited[v]++;
	if(fee > ans)
	{
		return ;
	}
	if(visited[n-1]==1)
	{
		if(fee < ans)
		{
			ans = fee;
		}
		return ;
	}
	for(int i = 0; i < tree[v].size(); i++)
	{
		t = tree[v][i];
		if(visited[t.c])
		{
			Dfs(t.b,t.p+fee);
			visited[t.b]--;
		}
		Dfs(t.b,t.r+fee);
		visited[t.b]--;
	}
}

int main()
{
	int i, m, a;
	node t;

	scanf("%d%d",&n,&m);
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%d%d%d",&a,&t.b,&t.c,&t.p,&t.r);
		a--,t.b--,t.c--;
		tree[a].push_back(t);
	}
	memset(visited,0,sizeof(visited));
	lim = 0;
	dfs(0);
	ans = lim;
	if(visited[n-1]==0)
	{
		puts("impossible");
		return 0;
	}
	memset(visited,0,sizeof(visited));
	Dfs(0,0);
	printf("%d\n",ans);
	return 0;
}