首页 > 代码库 > TSP(个人模版)
TSP(个人模版)
O(n^2)TSP:
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 #define INF 0x3f3f3f3f 7 int n,d[1005],dp[1005][1005]; 8 int dis(int a,int b) 9 { 10 int tmp=abs(d[a]-d[b]); 11 return min(tmp,360-tmp); 12 } 13 int TSP_Dp() 14 { 15 dp[2][1]=dis(1,2); 16 for (int i = 3; i <= n + 1; i++) { 17 dp[i][i-1] = INF; 18 19 for (int j = 1; j < i-1; j++) { 20 dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dis(i, j)); 21 dp[i][j] = dp[i-1][j] + dis(i, i-1); 22 } 23 } 24 25 int ans = INF; 26 for (int i = 1; i <= n; i++) 27 ans = min(ans, dp[n+1][i] + dis(n+1, i)); 28 return ans; 29 } 30 int main() 31 { 32 int t; 33 scanf("%d",&t); 34 while(t--) 35 { 36 d[1]=0; 37 int ans=0; 38 scanf("%d",&n); 39 for(int i=2;i<=n+1;i++) 40 { 41 int a; 42 scanf("%d%d",&a,&d[i]); 43 if(i==n+1)ans+=a*800; 44 ans+=10; 45 } 46 ans+=TSP_Dp(); 47 printf("%d\n",ans); 48 } 49 }
TSP(个人模版)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。