首页 > 试题广场 > 毕业旅行问题
[编程题]毕业旅行问题
小明目前在做一份毕业旅行的规划。打算从北京出发,分别去若干个城市,然后再回到北京,每个城市之间均乘坐高铁,且每个城市只去一次。由于经费有限,希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱,找到每个城市只访问一次并返回起点的最小车费花销。

输入描述:
城市个数n(1<n≤20,包括北京)

城市间的车票价钱 n行n列的矩阵 m[n][n]


输出描述:
最小车费花销 s
示例1

输入

4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0

输出

13

说明

共 4 个城市,城市 1 和城市 1 的车费为0,城市 1 和城市 2 之间的车费为 2,城市 1 和城市 3 之间的车费为 6,城市 1 和城市 4 之间的车费为 5,依次类推。假设任意两个城市之间均有单程票可购买,且票价在1000元以内,无需考虑极端情况。
哪位大佬可以添加个代码进行解析啊?这个问题一直不会啊!!!  看别人代码也看不懂啊!
发表于 2019-06-16 17:59:55 回复(2)

添加一个简单的Python版本吧。

思路和上面的大佬一样,但不知道为什么用Python会超时。

#TSP 状压DP

n = int(input())
m = []
for i in range(n):
    m.append(list(map(int, input().split())))

V = 1 << (n-1)  #从左至右每一位二进制代表第i个城市是否被访问 如1000代表,第一个城市被访问,而其他城市没有
dp = [[float("inf")] * V for i in range(n)] # dp[i][j]:从节点i只经过集合j所有点再回到0点所需要的最小开销

for i in range(n):
    dp[i][0] = m[i][0]

for j in range(1,V):
    for i in range(n):
        for k in range(1,n):  #能不能先到k城市
            if (j >> (k-1) & 1) == 1: #可以途径k
                dp[i][j] = min(dp[i][j], m[i][k] + dp[k][j ^ (1 << (k-1))])

#从0出发,经过所有点,再回到0的费用
print(dp[0][(1 << (n-1)) - 1])

发表于 2019-07-15 08:22:32 回复(1)
#include<bits/stdc++.h>
usingnamespacestd;
#define INF 999999
intmain()
{
    intdp[21][21];
    intn,s,i,j,k;
    inttemp,minx;
    while(scanf("%d",&n)!=EOF)
    {
        //int dp[n][n]={0};
        ints[n][1<<(n-1)];
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(j!=i) scanf("%d",&dp[i][j]);
                else
                {
                    scanf("%d",&dp[i][j]);
                    dp[i][j]=INF;
                }
            }
        }
        for(i=1;i<n;i++)
        {
            s[i][0]=dp[i][0];
        }
        for(j=1;j<1<<(n-1);j++)
        {
            for(i=1;i<n;i++)
            {
                if(((1<<(i-1))&j)==0)
                {
                    minx=INF;
                    for(k=1;k<n;k++)
                    {
                        if(((1<<(k-1))&j)!=0)
                        {
                            temp=dp[i][k]+s[k][j-(1<<(k-1))];
                            if(temp<minx)
                            {
                                minx=temp;
                            }
                        }
                    }
                }
                s[i][j]=minx;
            }
        }
        minx=INF;
        for(i=1;i<n;i++)
        {
            temp=dp[0][i]+s[i][((1<<(n-1))-1)-(1<<(i-1))];
            if(minx>temp)
            {
                minx=temp;
            }
        }
        printf("%d\n",minx);
    }
}
发表于 2019-08-09 15:33:19 回复(0)
不会,参考了前面的答案,为其添加了注释
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int getAns(vector<vector<int>> &nums){
    const int MAX = 0x0fffffff;
    int n = nums.size();
    int stateNum = 1 << n;
    // dp[i][j]中的i是一个二进制形式的数,表示经过城市的集合,如0111表示经过了城市0,1,2
    // dp[i][j]表示经过了i中的城市,并且以j结尾的路径长度
    vector<vector<int> > dp(stateNum,vector<int>(n,MAX));
    dp[1][0] = 0; //从城市0出发,所以经过城市0,以城市0结尾的路径为0
    //从城市0出发,更新和其他城市的距离
    for(int i=1;i<stateNum;i++){
        for(int j=0;j<n;j++){
            if(dp[i][j] != MAX){ //如果已经访问过
                for(int k=0;k<n;k++){
                    if( (i & (1 << k) ) == 0){ 
                        //没有访问过k,且从这里到k的距离小于原来的距离,则更新
                        dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k],dp[i][j] + nums[j][k]);
                    }
                }
            }
        }
    }
    int res = MAX;
    for(int i=1;i<n;i++){
        res = min(res,dp[stateNum-1][i] + nums[i][0]);
    }
    return res;
}
int main(int argc, char const *argv[])
{
   int n;
    while(cin>>n){
        vector<vector<int>> edges(n,vector<int>(n,0));
        int x;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin>>edges[i][j];
            }
        }
        cout<<getAns(edges)<<endl;
    }
    return 0;
}


发表于 2019-07-24 21:49:41 回复(0)
#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;
int minvalue = INT_MAX;

void backtrack(vector<vector<int> > arr, vector<int> place, vector<bool> visit,int sum,int n)
{
	if (place.size() == n)
	{
		if (arr[place[place.size() - 1]][0] != 0)
		{
			sum += arr[place[place.size() - 1]][0];
			if (sum < minvalue)
			{
				minvalue = sum;
			}
		}
		return;
	}
	int j = place[place.size() - 1];
	for (int i = 0; i < arr.size(); ++i)
	{
		if (arr[j][i] != 0&&visit[i]==false)
		{
			visit[i] = true;
			sum += arr[j][i];
			place.push_back(i);
			
			backtrack(arr, place, visit, sum, n);
			visit[i] = false;
			sum -= arr[j][i];
			place.pop_back();
			
		}
	}
}


int main(){
	int n;
	cin >> n;
	vector<vector<int> > arr(n, vector<int>(n, 0));
	for (int i = 0; i < n; ++i)//输入
		for (int j = 0; j < n; ++j)
		{
			cin >> arr[i][j];
		}
	vector<bool> visit(n, false);
	vector<int> place;
	place.push_back(0);
	visit[0] = true;
	int sum = 0;
	backtrack(arr, place, visit, sum, n);

	cout << minvalue << endl;
    return 0;
}
贴上递归代码,超时了。
发表于 今天 15:44:47 回复(0)
import java.util.Scanner;

/**
 * @作者:田九
 * @创建时间:2019年8月12日
 * @项目名称:algorithm.tsp_旅行商问题
 * @类名称:TSP2
 * @类描述:用动态规划的方法解决tsp问题

 */

/**动态规划模型构造
 * 对于4个城市的情况
城市的邻接表如下:
          S0  S1  S2  S3  
   S0   0   3    6     7
   S1   5   0    2     7   
   S2   6   6   0     2
   S3   3   3    5     0
假设找出的一条最短的回路:S0S1S2 S3S0
我们可以利用结论: "S1 S2 S3 S0 "必然是从S1到S0通过其它各点的一条最短路径(如果不是,则会出现矛盾)
Length(总回路) = Length(S0,S1)  + Length(S1,S2,S3,S0)

从上面的公式把总回路长度分解:
Length(回路) =Min{ Length(0,1)+Length(1,…,0), Length(0,2)+Length(2,…,0),Length(0,3)+Length(3,…,0)}
规范化地表达上面的公式
d(i,V) 表示从i点经过点集V各点一次之后回到出发点的最短距离
d(i,V') = min {Cik+d(k,V-{k})}   (k∈V') 
d(k,{ }) = Cik (k≠i)                          
其中,Cik表示i到k的距离     
从城市0出发,经城市1、2、3然后回到城市0的最短路径长度是:
d(0, {1, 2, 3})=min{C01+ d(1, { 2, 3}), C02+ d(2, {1, 3}),C03+ d(3, {1, 2})}

这是最后一个阶段的决策,它必须依据d(1, { 2, 3})、
d(2, {1, 3})和d(3, {1, 2})的计算结果,而: 

d(1, {2, 3})=min{C12+d(2, {3}),  C13+ d(3, {2})}
d(2, {1, 3})=min{C21+d(1, {3}),  C23+ d(3, {1})}
d(3, {1, 2})=min{C31+d(1, {2}),  C32+ d(2, {1})}
继续写下去:
d(1, {2})= C12+d(2, {})   d(2, {3})=C23+d(3, {})   d(3, {2})= C32+d(2, {})  
d(1, {3})= C13+d(3, {})   d(2, {1})=C21+d(1, {})   d(3, {1})= C31+d(1, {})

建立dp表

       
                            
*/
//对之前大佬代码的解读
//注意:经过的路线是一条经过所有城市的闭合回路, 因此从哪一点出发是无所谓的, 因此不妨设从城市0出发。
public class TSP2 {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int cityNum = in.nextInt();// 城市数目
        int[][] dist = new int[cityNum][cityNum];// 距离矩阵,距离为欧式空间距离
        for (int i = 0; i < dist.length; i++)
            for (int j = 0; j < cityNum; j++) {
                dist[i][j] = in.nextInt();
            }
        in.close();

        int V = 1 << (cityNum - 1);// 对1进行左移n-1位,值刚好等于2^(n-1)
        // dp表,n行,2^(n-1)列
        int[][] dp = new int[cityNum][V];
        // 初始化dp表第一列
        for (int i = 0; i < cityNum; i++)  dp[i][0] = dist[i][0];
        
        //设想一个数组城市子集V[j],长度为V,且V[j] = j,对于V[j]即为压缩状态的城市集合
        //从1到V-1  用二进制表示的话,刚好可以映射成除了0号城市外的剩余n-1个城市在不在子集V[j],1代表在,0代表不在
        //若有总共有4个城市的话,除了第0号城市,对于1-3号城市
        //111 = V-1 = 2^3 - 1  = 7 ,从高位到低位表示3到1号城市都在子集中
        //而101 = 5 ,表示3,1号城市在子集中,而其他城市不在子集中
        //这里j不仅是dp表的列坐标值,如上描述,j的二进制表示城市相应城市是否在子集中
        for (int j = 1; j < V; j++)   
            for (int i = 0; i < cityNum; i++) { //这个i不仅代表城市号,还代表第i次迭代
                dp[i][j] = Integer.MAX_VALUE; //为了方便求最小值,先将其设为最大值
                if (((j >> (i - 1)) & 1) == 0) { 
                    // 因为j就代表城市子集V[j],((j >> (i - 1))是把第i号城市取出来
                    //并位与上1,等于0,说明是从i号城市出发,经过城市子集V[j],回到起点0号城市
                    for (int k = 1; k < cityNum; k++) { // 这里要求经过子集V[j]里的城市回到0号城市的最小距离
                        if (((j >> (k - 1)) & 1) == 1) { //遍历城市子集V[j]
                            //设s=j ^ (1 << (k - 1))
                            //dp[k][j ^ (1 << (k - 1)),是将dp定位到,从k城市出发,经过城市子集V[s],回到0号城市所花费的最小距离
                            //怎么定位到城市子集V[s]呢,因为如果从k城市出发的,经过城市子集V[s]的话
                            //那么V[s]中肯定不包含k了,那么在j中把第k个城市置0就可以了,而j ^ (1 << (k - 1))的功能就是这个
                            dp[i][j] = Math.min(dp[i][j], dist[i][k] + dp[k][j ^ (1 << (k - 1))]); //^异或
                            //还有怎么保证dp[k][j ^ (1 << (k - 1))]的值已经得到了呢,
                            //注意所有的计算都是以dp表为准,从左往右从上往下的计算的,每次计算都用到左边列的数据
                            //而dp表是有初试值的,所以肯定能表格都能计算出来
                        }
                    }
                }
            }
        System.out.println(dp[0][V - 1]);
    }
}



编辑于 2019-08-13 17:47:03 回复(0)
这题内存卡得比较死,搞得我怀疑人生,最后发现题目数据应该是有问题,测试过n的范围在19以内。
经典的旅行商问题。
1. G[i][j]表示城市i到城市j的距离;
2. 用dp[i][k]表示当前在城市i,且经过的城市集合为k的最小总路程。集合可以表示为二进制,所以可以用整数k表示。例如j=11001,表示城市集合为{0,3,4}(二进制第0/3/4位为1)。注意,由于dp[i][k]表示为当前在城市i,所以k中必须包含i,即必有(1<<i) & k = 1。(1<<i) & k = 0的状态是不存在的,后面计算时要跳过;
3. 状态转移:dp[j][k | (1<<j)] = min{dp[j][k | (1<<j)], dp[i][k] + G[i][j]},即当前在城市i,经过的城市集合为k时,可以转移到城市j,花费的额外代价是G[i][j]。注意:a) k集合必须包含i,也就是二进制第i位必须为1,即(k>>i) & 1 = 1,或者说(1<<i) & k > 0;b) 因为每个城市只能走1次,k集合不能包含j,否则就说明当前这次转移前已经访问过城市j了,也就是必须满足 (1<<j) & k = 0;
4. 实现时,有2种办法,一种使用递归函数,另一种直接用循环来做。我们发现,状态转移方程中,等式左边的状态k | (1<<j)对应的整数值始终是大于右边的k的(为什么?因为在(1<<j) & k =0时,(1<<j) | k = k + (1<<j) > k),因此我们可以从小到大枚举状态1 ~ (1<<n)-1,对每个状态,考虑该状态可以转移出去的新状态。
5. 最终最小代价为min{dp[i][(1<<n)-1] + G[i][0]},即身处城市i,访问过的集合为{0, 1, 2, 3, ..., n-1}(对应二进制111...111=2^n-1)的总距离,再加上最后从城市i回到城市0的距离之和。我们希望得到上述距离和的最小值。
#include <cstdio>
#include <cstring>

const int MAX = 19;
short G[MAX][MAX];
short dp[MAX][1<<MAX];
 
int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%hd", &G[i][j]);
            }
        }

		memset(dp, 0x7f7f, sizeof(dp));
		// 初始状态是在城市0,访问集合是{0},即0000...00001
        dp[0][1] = 0;
        for (int k = 0; k < (1<<n)-1; k++) {
        	// 枚举所有状态k;当前已访问城市集合为k,当前在城市i,现在要访问另一个未访问过的城市j
        	for (int j = 0; j < n; j++) {
        		// k集合不能包含j
        		if ((1<<j)&k > 0) {
                    continue;
                }
	            for (int i = 0; i < n; i++) {
	            	// k集合必须包含i
                    if ((1<<i)&k == 0) {
                        continue;
                    } 
                    if (dp[i][k] + G[i][j] < dp[j][(1<<j)|k]) {
                    	dp[j][(1<<j)|k] = dp[i][k] + G[i][j];
                    }
                }
            }
        }
        int ans = 0xfffffff;
        for (int i = 1; i < n; i++) {
        	if (dp[i][(1<<n)-1] + G[i][0] < ans) {
        		ans = dp[i][(1<<n)-1] + G[i][0];
        	}
        }
        printf("%d\n", ans);
    }
    return 0;
}



发表于 2019-08-12 03:37:40 回复(0)
import java.util.HashSet; import java.util.Iterator; import java.util.Scanner;  public class ByteDance004 { public static void main(String args[]){
        Scanner in = new Scanner(System.in);  int n = Integer.parseInt(in.nextLine());  int[][] m = new int[n][n];  for (int i = 0; i < n; i ++){
            String[] str = in.nextLine().split(" ");  for(int j = 0; j <n; j++){
                m[i][j] = Integer.parseInt(str[j]);  }
        }
        HashSet<CityCount> set = new HashSet <>();  CityCount cityCount = new CityCount(0,0);  set.add(cityCount);  int s = 0;  for (int i=0; i < n; i++){ int a = 0;  int b = 0;  int cost = m[i][a] + m[i][b];  Iterator it = set.iterator();  CityCount cc = new CityCount(5,5);  while(it.hasNext()){
                CityCount tem = (CityCount)it.next();  int c = m[tem.getX()][i] + m[tem.getY()][i] - m[tem.getX()][tem.getY()];  if(c < cost){
                    a = tem.getX();  b= tem.getY();  cost = c;  }
                cc = tem;  }
            s+=cost;  set.remove(cc);  set.add(new CityCount(a,i));  set.add(new CityCount(i,a));  }
        System.out.println(s);   }
} class CityCount{ int x;  int y;  public CityCount(int a, int b){ x = a;  y = b;  } public int getX(){ return x;  } public int getY(){ return y;  }
}
发表于 2019-08-11 12:46:34 回复(0)
#蠢递归,只过了50%
#递归判断所有旅行路径的花费最小值
min_p = 100000
visit = []
def dfs(s,deepth,p,map,n):
    if deepth == n:
        global min_p
        min_p = min(p+map[s][0],min_p)
    
    for  j in range(len(map[s])):
        if visit[j] != 1:
            visit[j] = 1
            dfs(j,deepth+1,p+map[s][j],map,n)
            visit[j] = 0

n = int(input())
map = []
for i in range(n):
    row = [int(x) for x in input().strip().split()]
    map.append(row)
for j in range(n):
    visit.append(0)
for i in range(n):
    visit[i] = 1
    dfs(i,1,0,map,n)
print(min_p)
发表于 2019-08-11 11:36:01 回复(0)
自己的机器没问题,可能数据有误或者编译器问题
#include<iostream>
#include<vector>
#include<algorithm>
usingnamespacestd;
 
int** matrix;
 
intP(vector<int> remain)
{
    if(remain.size() == 1)
    {
        returnmatrix[remain[0]][0];//回家
    }
    else
    {
        intsource = remain.back();
        intbest = 50000;
        remain.pop_back();
        for(inti = 0; i < remain.size(); i++)
        {
            vector<int> newremain(remain);
            inttarget = remain[i];
            newremain.erase(newremain.begin() + i);
            newremain.push_back(target);
            intresult = P(newremain) + matrix[source][target];
            if(result < best)
            {
                best = result;
            }
        }
        returnbest;
    }
}
 
intmain()
{
    intN;
    cin >> N;
    matrix = (int**)malloc(N * sizeof(int));
    vector<int> remain;
    for(inti = 0; i < N; i++)
    {
        matrix[i] = (int*)malloc(N * sizeof(int));
        for(intj = 0; j < N; j++)
        {
            inttemp;
            cin >> temp;
            matrix[i][j] = temp;
        }
        remain.push_back(i+1);
    }
    remain.pop_back();
    remain.push_back(0);
    cout << P(remain);
 
    //system("pause");
    return0;
}
发表于 2019-07-31 21:18:08 回复(0)
方法二
动态规划 全部通过
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

int getAns(vector<vector<int>> &nums){
    
    int M = 0x7ffffff;
    int n = nums.size();
    vector<vector<int>> dp(1<<n, vector<int>(n,M));
    dp[1][0] = 0;
    for(int i=1; i<n; i++) dp[1<<i][i] = M;
    for(int i=1; i<(1<<n); i++){
        for(int j=0; j<n; j++){
            if(dp[i][j]!=M){
                for(int k=0; k<n; k++){
                    if((i&(1<<k))==0){
                        dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k], dp[i][j]+nums[j][k]);
                    }
                }
            }
        }
    }
    int ans = M;
    for(int i=1; i<n; i++){
        ans = min(ans, dp[(1<<n)-1][i]+nums[i][0]);
    }
    return ans;
}
int main(){
    int n;
    while(cin>>n){
        vector<vector<int>> edges(n,vector<int>(n,0));
        int x;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin>>edges[i][j];
            }
        }
        cout<<getAns(edges)<<endl;
    }
    return 0;
}


方法一 记忆化搜索只通过了50%
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
struct MyHash{
    size_t operator()(const pair<int,int> &x) const{
        return hash<int>()(x.first) && hash<int>()(x.second);
    }
};
int dp(vector<vector<int>> &nums, unordered_map<pair<int,int>, int, MyHash> &memo, pair<int,int> x, int M){
    if(memo.find(x)!=memo.end()) return memo[x];
    int ans = M;
    int n = nums.size();
    int last_state = x.first&(~(1<<x.second));
    for(int i=0; i<n; i++){
        if((last_state&(1<<i))==0) continue;
        ans = min(ans, nums[i][x.second]+dp(nums, memo, make_pair(last_state,i),M));
    }
    memo[x] = ans;
    return ans;
}
int getAns(vector<vector<int>> &nums){
    
    unordered_map<pair<int,int>,int, MyHash> memo;
    int n = nums.size();
    const int M = 0x7fffff;
    // 假设起点为0号节点
    memo[make_pair(1,0)] = 0;
    for(int i=1; i<n; i++){
        memo[make_pair(1<<i,i)] = M; //其它起点为非法状态
    }
    
    int ans = M;
    int tmp = (1<<n)-1;
    for(int i=1; i<n; i++){
        ans = min(ans, dp(nums, memo, make_pair(tmp, i), M)+nums[i][0]);
    }
    return ans;
}
int main(){
    int n;
    while(cin>>n){
        vector<vector<int>> edges(n,vector<int>(n,0));
        int x;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin>>edges[i][j];
            }
        }
        cout<<getAns(edges)<<endl;
    }
    return 0;
}

编辑于 2019-07-07 22:59:39 回复(0)
public class Main{
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] map = new int[n][n];
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                map[i][j] = in.nextInt();
            }
        }
        //dp[i][j]表示从i出发,经过j集合里的所有节点一次回到0点的最小小费
        int V = 1<<(n-1);  //
        int[][] dp = new int[n][V];
        for(int i=0;i<n;i++) {     // 先求dp表第一列
            dp[i][0] = map[i][0];   //每个城市回到起点的距离
        }

        for(int j=1;j<V;j++) {                  // 再求其他列
            for(int i=0;i<n;i++) {              //从i出发,要去包含j = {010101} 的城市
//                dp[i][j] = 100000;               //或者用 0x7ffff表示无穷大
                dp[i][j] = 0x7ffff;
                if(((j >> (i-1)) & 1) == 1) {    //如果已经到过j了,就continue跳出循环
                    continue;
                }
                for(int k=1;k<n;k++) {          //看能不能先到k城市
                    if(((j >> (k-1)) & 1) == 1) {  //能到
                        dp[i][j] = Math.min(dp[i][j], map[i][k] + dp[k][j ^ (1 << (k-1))]);
                    }
                }
            }
        }
        System.out.println(dp[0][(1 << (n-1))-1]);

        /*
         *以下为打印dp表
         */
        System.out.printf("%10d",0);
        for(int j = 0;j < 1 << (n - 1) ;j++){
            System.out.printf("%10d",j);
        }
        System.out.println();
        for(int i = 0;i < n;i++){
            System.out.printf("%10d",i);
            for(int j = 0;j < 1 << (n - 1) ;j++){
                if(dp[i][j] == 0x7ffff) dp[i][j] = -1;
                System.out.printf("%10d",dp[i][j]);
            }
            System.out.println();
        }

    }
}
编辑于 2019-07-06 16:24:53 回复(0)
用例:
5
0 3 4 2 7
3 0 4 6 3
4 4 0 5 8
2 6 5 0 6
7 3 8 6 0
对应输出应该为:
19
你的输出为:
21
这个样例的结果是不是有问题啊,我看了挺久都是21吧,输出
发表于 2019-07-04 16:41:44 回复(0)
这题样例有问题,直接开f[1<<20][20]爆内存,自动生成f[1<<n][n]不会爆内存.至于解析可以搜关键词:哈密尔顿路,旅行商问题,状压dp
发表于 2019-07-04 16:28:43 回复(0)
import java.util.Scanner;

/** 
* @author 小炉子 863956237@qq.com: 
* @version
创建时间:2019年6月21日 下午8:43:30 
* 类说明 
*/
public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] map = new int[n][n];
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                map[i][j] = in.nextInt();
            }
        }
        int V = 1<<(n-1);
        int[][] dp = new int[n][V];
        for(int i=0;i<n;i++) {
            dp[i][0] = map[i][0];
        }
        
        for(int j=1;j<V;j++) {
            for(int i=0;i<n;i++) {
                dp[i][j] = 100000;
                if(((j >> (i-1)) & 1) == 1) {
                    continue;
                }
                for(int k=1;k<n;k++) {
                    if(((j >> (k-1)) & 1) == 1) {
                        dp[i][j] = Math.min(dp[i][j], map[i][k] + dp[k][j ^ (1 << (k-1))]);
                    }
                }
            }
        }
        System.out.println(dp[0][(1 << (n-1))-1]);

    }
}
发表于 2019-06-21 21:11:41 回复(2)
#include <iostream>
using namespace std;

int main()
{
	int cityCount;
	cin >> cityCount;
	int ** roadmap = new int* [cityCount];
	for (int i = 0; i < cityCount; i++) roadmap[i] = new int[cityCount]; //记得要循环做析构
	for(int i=0; i<citycount>> roadmap[i][j];
		}

	int **dp = new int*[cityCount];
	for (int i = 0; i < cityCount; i++) dp[i] = new int[1 << (cityCount - 1)];
	
	for (int i = 0; i < cityCount; i++) { dp[i][0] = roadmap[i][0]; }
	for (int i = 0; i < cityCount; i++) { dp[i][1] = roadmap[i][1] + dp[1][0]; }
	for (int j = 1; j < 1 << (cityCount - 1); j++)
		for (int i = 0; i < cityCount; i++) {
			dp[i][j] = 0x7ffff;
		}
	//for (int i = 0; i < cityCount; i++) { cout << dp[i][1] << endl; }

	for (int j = 1; j < 1 << (cityCount - 1); j++)
		for (int i = 0; i< cityCount; i++) {
			if ((j << (i - 1)) & 1 == 1) { continue; }
			for (int k = 1; k < cityCount; k++) {
				if ((j << (k - 1)) & 1 == 0) { continue; }
				// cout << dp[k][j ^ (1 << (k - 1))] << endl;
				if (dp[i][j] > roadmap[i][k] + dp[k][j ^ (1 << (k - 1))])
					dp[i][j] = roadmap[i][k] + dp[k][j ^ (1 << (k - 1))];
			}
		}

	cout << dp[0][(1 << (cityCount - 1)) - 1];
    return 0;
}


</citycount></iostream>
编辑于 2019-06-16 18:35:33 回复(1)