Untitled
unknown
plain_text
2 months ago
1.5 kB
4
Indexable
#include <bits/stdc++.h> using namespace std; void File() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } const int inf=1e9; void solve() { int x,y,st,ed,m;cin>>x>>y>>st>>ed>>m; vector<pair<int,int>>p; p.push_back({st,ed}); for (int i = 0; i < m; ++i) { int a,b;cin>>a>>b; p.push_back({a,b}); } vector<vector<int>>dis(p.size(),vector<int>(p.size(),inf)); for (int i = 0; i < p.size(); ++i) for (int j = 0; j < p.size(); ++j) dis[i][j]=abs(p[i].first-p[j].first)+abs(p[i].second-p[j].second); for (int k = 0; k < p.size(); ++k) for (int i = 0; i < p.size(); ++i) for (int j = 0; j < p.size(); ++j) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); int n=p.size(); int dp[n][1<<n]; memset(dp,-1,sizeof dp); function<int(int,int)> tsp=[&](int i,int msk)->int{ if(__builtin_popcount(msk)==p.size()) return dis[i][0]; int &ret=dp[i][msk]; if(~ret)return ret; ret=inf; for (int j = 0; j < p.size(); ++j) if(!(msk&(1<<j))) ret=min(ret,tsp(j,msk|(1<<j))+dis[i][j]); return ret; }; cout<<"The shortest path has length "<<tsp(0,1)<<'\n'; } signed main() { File(); int t;cin>>t; while(t--) solve(); }
Editor is loading...
Leave a Comment