Untitled
unknown
plain_text
9 months ago
1.2 kB
1
Indexable
#include <iostream> using namespace std; #pragma warning (disable:4996) int sx,sy,hx,hy,n,min1; int visit[20]; int weight[20][20]; struct Point{ int x; int y; }; Point a[20]; void backtrack(int vitri, int dem, int kq){ if (dem==n){ if (kq+weight[vitri][n+1]<min1){ min1=kq+weight[vitri][n+1]; } return; } if (kq+weight[vitri][n+1]>min1){ return; } for (int i=1; i<=n; i++){ if (visit[i]==0){ visit[i]=1; backtrack(i,dem+1,kq+weight[vitri][i]); visit[i]=0; } } }; int main(){ freopen("Text.txt","r",stdin); int tc; cin >>tc; for (int t=1; t<=tc; t++){ cin >> sx >> sy >> hx >> hy; cin >> n; a[0].x=sx; a[0].y=sy; a[n+1].x=hx; a[n+1].y=hy; visit[0]=0; visit[n+1]=0; for (int i=1; i<=n; i++){ cin >> a[i].x >> a[i].y; visit[i]=0; } for (int i=0; i<n+1; i++){ for (int j=i+1; j<=n+1; j++){ int u,v; if (a[i].x-a[j].x >=0){ u=a[i].x-a[j].x; } else{ u=a[j].x-a[i].x; } if (a[i].y-a[j].y >=0){ v=a[i].y-a[j].y; } else{ v=a[j].y-a[i].y; } weight[i][j]=u+v; weight[j][i]=u+v; } } min1=10000000; backtrack(0,0,0); cout<<"Case #"<<t<<" "<<min1<<endl; } return 0; }
Editor is loading...
Leave a Comment