TSP问题
Time Limit : 1 sec , Memory Limit : 128MB Description
对于给定的加权有向图G(V,E),查找满足以下条件的最短路径的距离: 这条路径是一个环,即这条路径的起点和终点都是同一个点。 每个顶点只能访问一次。
Input
|V| |E|
s0 t0 d0
s1 t1 d1
:
s|E|−1 t|E|−1 d|E|−1
|V| 是顶点数,|E|是边数。顶点以数字 0, 1,..., |V|-1表示。 si 和ti 表示第i条边(有向)的源和目标顶点,di 表示si和 ti (第i条边)之间的距离。
Output
在一行中输出最短距离。如果没有解决方案,则输出 -1。
Constraints
2 ≤ |V| ≤ 15 0 ≤ di ≤ 1,000 没有多重边
Sample Input 1
4 6
0 1 2
1 2 3
1 3 9
2 0 1
2 3 6
3 2 4
Sample Output 1
16
Sample Input 2
3 3
0 1 1
1 2 1
0 2 1
Sample Output 2
-1
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAX_N 16 #define INF 0xfffffff using namespace std; int n; int d[MAX_N][MAX_N]; int dp[1 << MAX_N][MAX_N]; //记忆化搜索使用的 DP数组 //已经访问过的顶点集合为 S,当前位置为 v int rec(int S, int v) { if (dp[S][v] >= 0) return dp[S][v]; if (S == (1 << n) - 1 && v == 0) { //已访问过所有顶点并回到 0号起点 return dp[S][v] = 0; //访问所有节点后回溯 将所有边的值相加 } int res = INF; //无穷大值 for (int u = 0; u < n; u++) { // 当前集合中不包含该点 且 当前点到该点有边 if (!(S >> u & 1) && d[v][u] != 1061109567) { res = min(res,rec(S | 1 << u, u) + d[v][u]); } } return dp[S][v] = res; //动归方程: dp[S][v] = min(dp[S][v],dp[S | {u}][u] + dis[u][v]) (S >> u & 1 ==0) } void solve() { memset(dp, -1, sizeof(dp));//初始化为 -1 以免边长为0的边干扰 int ans = rec(0,0); if(ans == INF)printf("-1"); else printf("%d",ans); } int main() { //freopen("tsp.in","r",stdin); //freopen("tsp.out","w",stdout); int m,x,y,t; memset(d,0x3f,sizeof(d));//初始化为INF 避免边长为0的边干扰 cin>>n>>m; for(int i=1;i<=m;i++) { cin>>x>>y>>t; d[x][y] = t; } solve(); }