Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int x2, y2;
- int n, ans;
- int a[102][5];
- void warmhole(int x1, int y1, int ind, int cost){
- if(ind==n){//If ind is greater than or equal to n, it means all warmholes have been considered.
- cost+=abs(x1-x2)+abs(y1-y2);//calculates the cost to travel from the current point to the destination
- ans=min(ans, cost);
- return;
- }
- int c1 = cost+abs(x1-a[ind][0])+abs(y1-a[ind][1])+a[ind][4];//c1 is the cost of moving from the current point to the warmhole's entry point
- int c2 = cost+abs(x1-a[ind][2])+abs(y1-a[ind][3])+a[ind][4];//c2 is the cost of moving from the current point to the warmhole's exit point
- if(c1<=c2 and c1<ans){
- warmhole(a[ind][2], a[ind][3], ind+1, c1);
- }
- else if(c2<ans){
- warmhole(a[ind][0], a[ind][1], ind+1, c2);
- }
- if(cost<ans){
- warmhole(x1, y1, ind+1, cost);//current warmhole is skipped.
- }
- }
- int main(){
- int t;
- cin >> t;
- while(t--){
- int x1, y1;
- cin >> n;
- cin >> x1 >> y1 >> x2 >> y2;
- for(int i=0; i<n; i++){
- cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3] >> a[i][4];
- }
- ans=INT_MAX;
- warmhole(x1, y1, 0, 0);
- cout << ans << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement