编程介的小学生
2018-12-05 03:51
采纳率: 92.7%
浏览 1.1k

数据结构,哈密尔顿路径的问题,用C语言

Problem Description
Give you a Graph,you have to start at the city with ID zero.

Input
The first line is n(1<=n<=21) m(0<=m<=3)
The next n line show you the graph, each line has n integers.
The jth integers means the length to city j.if the number is -1 means there is no way. If i==j the number must be -1.You can assume that the length will not larger than 10000
Next m lines,each line has two integers a,b (0<=a,b<n) means the path must visit city a first.
The input end with EOF.

Output
For each test case,output the shorest length of the hamilton path.
If you could not find a path, output -1

Sample Input
3 0
-1 2 4
-1 -1 2
1 3 -1
4 3
-1 2 -1 1
2 -1 2 1
4 3 -1 1
3 2 3 -1
1 3
0 1
2 3

Sample Output
4
5

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • blownewbee 2019-03-28 10:45
    已采纳
    点赞 评论
  • szh_0808 2018-12-05 07:21

    哈密尔顿路径不应该状压DP么。f[i][S]表示当前在i号点,访问的点的状态为S是否可行,转移枚举出边即可吧

    点赞 评论

相关推荐 更多相似问题