HDU 2224 The shortest path
The HDU path Shortest
2023-09-11 14:15:28 时间
The shortest path
Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 222464-bit integer IO format: %I64d Java class name: Main
There are n points on the plane, Pi(xi, yi)(1 <= i <= n), and xi < xj (i<j). You begin at P1 and visit all points then back to P1. But there is a constraint:
Before you reach the rightmost point Pn, you can only visit the points those have the bigger x-coordinate value. For example, you are at Pi now, then you can only visit Pj(j > i). When you reach Pn, the rule is changed, from now on you can only visit the points those have the smaller x-coordinate value than the point you are in now, for example, you are at Pi now, then you can only visit Pj(j < i). And in the end you back to P1 and the tour is over.
You should visit all points in this tour and you can visit every point only once.
Before you reach the rightmost point Pn, you can only visit the points those have the bigger x-coordinate value. For example, you are at Pi now, then you can only visit Pj(j > i). When you reach Pn, the rule is changed, from now on you can only visit the points those have the smaller x-coordinate value than the point you are in now, for example, you are at Pi now, then you can only visit Pj(j < i). And in the end you back to P1 and the tour is over.
You should visit all points in this tour and you can visit every point only once.
Input
The input consists of multiple test cases. Each case begins with a line containing a positive integer n(2 <= n <= 200), means the number of points. Then following n lines each containing two positive integers Pi(xi, yi), indicating the coordinate of the i-th point in the plane.
Output
For each test case, output one line containing the shortest path to visit all the points with the rule mentioned above.The answer should accurate up to 2 decimal places.
Sample Input
3 1 1 2 3 3 1
Sample Output
6.47 Hint: The way 1 - 3 - 2 - 1 makes the shortest path.
解题:双调TSP
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int INF = 0x3f3f3f3f; 4 const int maxn = 500; 5 typedef long long LL; 6 double dp[maxn][maxn],ds[maxn][maxn]; 7 struct Point { 8 int x,y; 9 bool operator<(const Point &t) const { 10 return x < t.x; 11 } 12 } p[maxn]; 13 double calc(int a,int b) { 14 LL x = p[a].x - p[b].x; 15 LL y = p[a].y - p[b].y; 16 double tmp = x*x + y*y; 17 return sqrt(tmp); 18 } 19 20 int main() { 21 int n; 22 while(~scanf("%d",&n)) { 23 for(int i = 1; i <= n; ++i) 24 scanf("%d%d",&p[i].x,&p[i].y); 25 sort(p,p+n); 26 for(int i = 1; i <= n; ++i) 27 for(int j = 1; j <= n; ++j) 28 ds[i][j] = calc(i,j); 29 dp[2][1] = ds[1][2]; 30 for(int i = 3; i <= n; ++i) { 31 dp[i][i-1] = INF; 32 for(int j = 1; j < i - 1; j++) { 33 dp[i][j] = dp[i-1][j] + ds[i][i-1]; 34 dp[i][i-1] = min(dp[i][i-1],dp[i-1][j] + ds[j][i]); 35 } 36 } 37 printf("%.2f\n",dp[n][n-1]+ds[n-1][n]); 38 } 39 return 0; 40 }
相关文章
- The superclass"javax.servlet.http.HttpServlet" was not found on the Java Build Path
- multiple web application host under the same website on IIS (authentication mode)
- pkg_resources.DistributionNotFound: distribution was not found and is required by the application
- 2015 Multi-University Training Contest 8 hdu 5385 The path
- 启动简单的springboot项目报错:To display the conditions report re-run your..Web server failed to start
- Xamarin.iOS项目编译提示Could not AOT the assembly
- Nignx出现failed (3: The system cannot find the path specified)问题
- HDU 4126 Genghis Khan the Conqueror (树形DP+MST)
- HDU 3666 THE MATRIX PROBLEM (差分约束)
- Why am I able to change the contents of const char *ptr?
- The Swift Programming Language--语言指南--协议
- The superclass "javax.servlet.http.HttpServlet" was not found on the Java Build Path
- 【hacker的错误集】html5lib使用报错Couldn‘t find a tree builder with the features you requested: html5lib
- The attribute required is undefined for the annotation type XmlElementRef
- 【HDU - 4344】Mark the Rope(大整数分解)
- Unity 报错之 The type or namespace name ‘UI‘ does not exist in the namespace ‘UnityEngine‘
- HDU 1010 Tempter of the Bone heuristic 修剪
- nyoj 484-The Famous Clock
- The LMAX disruptor Architecture--转载
- The model backing the context has changed since the database was created.
- Eclipse Maven项目出现“The superclass "javax.servlet.http.HttpServlet" was not found on the Java Build Path”
- Eclipse中使用MySql遇到:Loading class `com.mysql.jdbc.Driver'. This is deprecated. The new driver class is `com.mysql.cj.jdbc.Driver'. The driver is automatically registered via the SPI and manual loading o
- IIS 报错 Cannot open database "test4" requested by the login. The login failed. Login failed for user 'IIS APPPOOLtest1'.
- java.lang.IllegalArgumentException: Invalid character found in the request target. The valid characters are defined in RFC 7230 and RFC 3986
- H - the Sum of Cube(水题)