Shortest Rectilinear Visiting Path
National Olympiad — Municipal round (2011 season)
Submission name: line.cpp
Problem summary
Find the minimum length of an open polyline that visits every given point and uses only horizontal and vertical segments. You may choose its starting and ending points freely.
Input
N, followed by N pairs of integer coordinates.
Output
The minimum total length.
Constraints
2 ≤ N ≤ 9; 1 ≤ x,y ≤ 9.
Worked example
An independently prepared example for this explanation.
Input
3 1 2 2 6 5 2
Output
9
Solution analysis
- Between points (x1,y1) and (x2,y2), every horizontal/vertical route has length at least |x1−x2|+|y1−y2|. Moving horizontally and then vertically attains that Manhattan distance.
- Choose the order in which points are visited. Since N is small, let dp[mask][last] be the minimum length after visiting the indexed points in mask and ending at last. Initialize every one-point state to zero, since the start is free.
- From a state, append an unvisited point next and add their Manhattan distance. The answer is the smallest full-mask state; there is no requirement to return to the start.
- For (1,2),(2,6),(5,2), visit (2,6) → (1,2) → (5,2). The distances are 5 and 4, giving 9. A shortest connection may pass another point incidentally; this does not invalidate a route that visits all points.
Why it works
Any feasible polyline has an order of first visits to the input points. Each part between consecutive first visits costs at least their Manhattan distance, so the DP optimum is a lower bound on every route. Conversely, an order produced by the DP can be connected by shortest rectilinear segments, producing a feasible route of exactly that DP cost. Thus the two optima agree.
Watch out. This is an open visiting path, not a tour: do not add a return edge. Use Manhattan distance rather than Euclidean distance. Initialize every possible starting point. Coincident input points simply have distance zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>x(n),y(n);
for(int i=0;i<n;++i){
cin>>x[i]>>y[i];
}
const int infinity=1000000;
int states=1<<n;
vector<vector<int>>dp(states,vector<int>(n,infinity));
// The starting point is unrestricted and costs no movement.
for(int start=0;start<n;++start){
dp[1<<start][start]=0;
}
for(int mask=1;mask<states;++mask){
for(int last=0;last<n;++last){
if(dp[mask][last]==infinity){
continue;
}
for(int next=0;next<n;++next){
if((mask&(1<<next))!=0){
continue;
}
int distance=abs(x[last]-x[next])+abs(y[last]-y[next]);
int nextMask=mask|(1<<next);
dp[nextMask][next]=min(dp[nextMask][next],dp[mask][last]+distance);
}
}
}
cout<<*min_element(dp.back().begin(),dp.back().end())<<'\n';
}