YCOJ中国邮递员问题

题目：

Description

一个邮递员从邮局出发，需要去 n - 2个城市送信，送完信件以后回家。

邮局在城市 1，家在城市 n，任意两个城市之间都有道路，但是这些道路是单向，也就是说 a 到 b 和 b 到 a 的路径长度不一定是一样的。

他必须经过每个城市一次，并且不能重复经过，最后回到家里。

现在要求你计算他需要经过的路径总和的最小长度。

Input

第一行有一个整数 n(2≤ n ≤ 10)。

接下里输入一个 n × n 的邻接矩阵 G, G[i][j] 表示从 i 走到 j 的路径长度。

Output

输出一个整数表示最小经过的路径总长度。

Sample Input 1 

4

0 1 1 1

1 0 2 1

5 5 0 6

1 1 3 0

Sample Output 1

7

Source

计蒜客

当我第一眼看到这道题时，顿时傻眼了这是什么题啊？

 a 到 b 和 b 到 a 的路径长度不一定是一样的。

这是几个意思？算了，我们可是OIer，不要用正常人的眼光来看这些题。

也就是说，这道题的图是一个有向图，所以又要请出我们的动态数组vector了。

这道题的大致思路就是DFS求出所有方案数，求出一个和目前已知最优方案比一下。

具体代码：

#include <bits/stdc++.h>

using namespace std;

int n;

bool vis[1010];

struct node{

	int v;

	int w;

	node(){};

	node(int _v,int _w){

		v=_v;

		w=_w;

	} //构造函数

};//

int ans=0x3f3f3f3f;

vector <node>g[15];

void dfs(int u,int k,int sum){

	if(u==n&&k==n){

		ans=min(ans,sum);

		return;

	}//走完了，和目前已知最小值比一下

	vis[u]=1;

	for (int i=0;i<g[u].size();i++){

		if(!vis[g[u][i].v]){

			dfs(g[u][i].v,k+1,sum+g[u][i].w);//代码核心

		}

	}

	vis[u]=0;

}

int main(){

	cin >>n;

	for (int i=1;i<=n;i++){

		for (int j=1;j<=n;j++){

			int w;

			cin>>w;

			g[i].push_back(node(j,w));//放进动态数组

		}

	}

	dfs(1,1,0);//调用函数

	cout << ans;

	return 0;

}

巴特西

YCOJ中国邮递员问题

最新文章

热门文章