CDCR2015-Sadiq on a Date-EDITORIAL

general
1

Contest link
[Contest][1]

Difficulty: Med-hard

Explanation

We will use binary search to find the answer. Further we will use Ford-Bellman algorithm. On each step we will have an array of maximum values on timer, when we stand in some point. On in transfer we will check: will our player stay alive after travelling beetwen points. If we can make transfer, we will update value of the final destination point. Becouse of a_i<=d and integer coordinates we haven’t optimal cycles, and solution exists.Check the Following code for better understanding
[1]: CodeChef: Practical coding for everyone

int func(int r, int n, int d) {
    int s, i, j;
    memset(vis, 0, sizeof(vis));
    memset(dis, 0, sizeof(dis));
    priority_queue <pp, vector , Prioritize> q;
    q.push(pp(0, r));
    dis[0] = 0;
    while (!q.empty()) {
        s = q.top().first;
        r = q.top().second;
        r += a[s];
        q.pop();
        if (vis[s])
            continue;
        //cout << s << " " << dis[s] << " " << r << endl;
        vis[s] = 1;
        for (i = 1; i < n; i++) {
            if (!vis[i]){
                j = (abs(p[i].x - p[s].x) + abs(p[i].y - p[s].y))*d;
                //cout <" << j << " " << dis[i] << " " << i <= dis[i])) {
                    dis[i] = r - j;
                    q.push(pp(i, dis[i]));
                }
            }
        }
    }
    if (vis[n - 1])
        return 1;
    else
        return 0;
}

void bsearch()
{
    s = 1;
    e = INF;
    while (s < e) {
        mid = (s + e) / 2;
        j = func(mid, n, d);
      
        if (j == 1) {
            e = mid;
        }
        else
            s = mid + 1;
    }
    cout << e << endl;
    
}