Trains

MRT Corp has recently hired you, one of the most talented programmers in the country, to assist in building MRT tracks in the country.

To begin with, you are given a square grid map of size N x N​, detailing the number of people, C residing in each grid segment. Since constructing your tracks would require all inhabitants of the utilized land to relocate, you are to decide on a potential railway connecting train stations A ​and B​, with the coordinates (A_x, A_y) and (B_x, B_y) respectively, such that the number of people forced to relocate are kept to a minimum and output that number. Do note that there may be certain areas in which you cannot build your train tracks (e.g. unstable land, hills etc.).

You are also reminded that you cannot build diagonal train tracks and only build in the 4 main directions (e.g. left, right, up, down).

Problem Source : MCO 2015

Input

Line 1: An integer N​, the length of the square grid of the map.
Line 2: Four integers A_x, A_y, B_x​ and B_y​ which signifies the x and y-coordinates (from top-left to bottom-right) of the two stations A and B. You will be guaranteed that the two train stations will be situated at distinct locations.
Line 3 to (N+​2): N​ integers with a value, C ​each detailing the number of inhabitants of a particular area and separated by spaces. Areas in which you are not allowed to build train tracks on will be given a value of -1.

Output

A single line stating the minimum number of inhabitants that will have to be relocated. Output -1 if it is impossible to construct the tracks without building on the areas in which you are not allowed to build tracks.

Constraints

  • Time Limit : 1s
  • Memory Limit : 64 MB
  • 2\leq N \leq 400
  • 1 \leq A_x, A_y, B_x, B_y \leq N
  • -1 \leq C \leq 1,000,000

Sample Input

5
1 3 5 4
10 30 20 50 10
10 20 -1 25 10
99 10 -1 10 10
10 10 -1 10 10
10 10 -1 99 12

Sample Output

363

Explanation

The path is [99, 10, 10, 30, 20, 50, 25, 10, 10 ,99] with sum of cost 363.

Solution

The idea is to explore every neighboring nodes from the starting points. Each time, update their data, store them into a priority queue and mark them as visited. Using this method, every visited node will be in its lowest possible cost. Repeat this steps until the ending node is reached or the entire graph has been visited.

C++

#include <cstdio>
#include <queue>

using namespace std;

struct node{
    long long cost;
    int x, y;
    bool v;
};

class CompareCost{ public:
    bool operator()(node a, node b){
        if (a.cost > b.cost) return true;
        else return false;
    }
};

node a[400][400];
priority_queue< node, vector<node>, CompareCost > pq;

int N, Ax, Ay, Bx, By, i, j;
node k;

int main(){

    scanf("%d%d%d%d%d", &N, &Ax, &Ay, &Bx, &By);
    Ax--; Ay--; Bx--; By--;

    for (i=0; i<400; i++){
        for (j=0; j<400; j++){
            a[i][j].v = 1;    // 1 for cannot be visited
        }
    }

    for (i=0; i<N; i++){
        for (j=0; j<N; j++){
            scanf("%lld", &a[i][j].cost);
            a[i][j].x = j;
            a[i][j].y = i;

            if (a[i][j].cost != -1) a[i][j].v = 0;
        }
    }

    pq.push(a[Ay][Ax]);
    a[Ay][Ax].v = 1;

    while (!pq.empty()){

        if (a[By][Bx].v) break;

        k = pq.top(); pq.pop();

        if (k.y+1 < N && !a[k.y+1][k.x].v){
            a[k.y+1][k.x].cost += k.cost;
            pq.push(a[k.y+1][k.x]);
            a[k.y+1][k.x].v = 1;
        }
        if (k.y-1 >= 0 && !a[k.y-1][k.x].v){
            a[k.y-1][k.x].cost += k.cost;
            pq.push(a[k.y-1][k.x]);
            a[k.y-1][k.x].v = 1;
        }
        if (k.x+1 < N && !a[k.y][k.x+1].v){
            a[k.y][k.x+1].cost += k.cost;
            pq.push(a[k.y][k.x+1]);
            a[k.y][k.x+1].v = 1;
        }
        if (k.x-1 >= 0 && !a[k.y][k.x-1].v){
            a[k.y][k.x-1].cost += k.cost;
            pq.push(a[k.y][k.x-1]);
            a[k.y][k.x-1].v = 1;
        }
    }

    if (a[By][Bx].v && a[Ay][Ax].cost != -1){
        printf("%lld",a[By][Bx].cost);
    }
    else printf("%d",-1);

    return 0;
}
Advertisements
Trains

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s