Warmholes

#include<bits/stdc++.h>
using namespace std;

int x2, y2, n, ans;
int a[105][5];
vector<int>seen;

void solve(int x1, int y1, int ind, int cost){
    if(ind == n){
        int x = abs(x1 - x2) + abs(y1-y2);
        ans = min(ans, x+cost);
        return;
    }

    int c1 = cost + abs(x1 - a[ind][0]) + abs(y1 - a[ind][1]) + a[ind][4];
    int c2 = cost + abs(x1 - a[ind][2]) + abs(y1 - a[ind][3]) + a[ind][4];

    if(c1 <= c2 and c1 < ans){
        solve(a[ind][2], a[ind][3], ind+1, c1);
    }
    else if(c2 < ans){
        solve(a[ind][0], a[ind][1], ind+1, c2);
    }
    if(cost < ans){
        solve(x1, y1, ind+1, cost);
    }
}

int main(){
    int tc;
    cin >> tc;
    while(tc--){

        cin >> n;
        int x1, y1;
        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;
        solve(x1, y1, 0, 0);
        cout << ans << endl;
    }

    return 0;

}

/*1
3
0 0 100 100
1 2 120 120 16
2 5 120 100 21
6 8 150 180 16

48
*/