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

Egg Dropping Problem

Suppose you have two eggs and you want to determine from which floors in a one-hundred floor building you can drop an egg such that it doesn’t break. You are to determine the minimum number of attempts you need in order find the critical floor in the worst case while using the best strategy.

  • If the egg doesn’t break at a certain floor, it will not break at any floor below.
  • If the eggs breaks at a certain floor, it will break at any floor above.
  • The egg may break at the first floor.
  • The egg may not break at the last floor.

Continue reading “Egg Dropping Problem”

Egg Dropping Problem

Shipping Routes

The Slow Boat to China Shipping company needs a program to help them quickly quote costs to prospective customers. The cost of a shipment depends on the size of the shipment and on how many shipping legs it requires. A shipping leg connects two warehouses, but since every pair of warehouses is not directly connected by a leg, it might require more than one leg to send a shipment from one warehouse to another.

A data set can represent from 1 to 30 warehouses. A two-letter code name will identify each warehouse (capital letters only). Shipping legs can exist between any two distinct warehouses. All legs are bidirectional.

The cost of a shipment is equal to the size of the shipment times the number of shipping legs required times $100.

The input to the program identifies the warehouse code names and the existence of all shipping legs. For a given shipping request, consisting of the size of the shipment, the source warehouse and the destination warehouse, the program will output the best (cheapest) cost for the shipment, if it is possible to send shipments from the requested source to the requested destination. Alternately, the program must state that the request cannot be fulfilled.

Continue reading “Shipping Routes”

Shipping Routes

A Node Too Far – Revisited

To avoid the potential problem of network messages (packets) looping around forever inside a network, each message includes a Time To Live (TTL) field. This field contains the number of nodes (stations, computers, etc.) that can retransmit the message, forwarding it along toward its destination, before the message is unceremoniously dropped. Each time a station receives a message it decrements the TTL field by 1. If the destination of the message is the current station, then the TTL field’s value is ignored. However, if the message must be forwarded, and the decremented TTL field contains zero, then the message is not forwarded.

In this problem you are given the description of a number of networks, and for each network you are asked to determine the number of nodes that are not reachable given an initial node and TTL field value.

Continue reading “A Node Too Far – Revisited”

A Node Too Far – Revisited

A Node Too Far

To avoid the potential problem of network messages (packets) looping around forever inside a network, each message includes a Time To Live (TTL) field. This field contains the number of nodes (stations, computers, etc.) that can retransmit the message, forwarding it along toward its destination, before the message is unceremoniously dropped. Each time a station receives a message it decrements the TTL field by 1. If the destination of the message is the current station, then the TTL field’s value is ignored. However, if the message must be forwarded, and the decremented TTL field contains zero, then the message is not forwarded.

In this problem you are given the description of a number of networks, and for each network you are asked to determine the number of nodes that are not reachable given an initial node and TTL field value.

Continue reading “A Node Too Far”

A Node Too Far