POJ 2502: Subway

-

Subway

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 10066 Accepted: 3289

Description


You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to ride your bike to school every day, you now get to walk and take the subway. Because you don't want to be late for class, you want to know how long it will take you to get to school.
You walk at a speed of 10 km/h. The subway travels at 40 km/h. Assume that you are lucky, and whenever you arrive at a subway station, a train is there that you can board immediately. You may get on and off the subway any number of times, and you may switch between different subway lines if you wish. All subway lines go in both directions.
Input

Input consists of the x,y coordinates of your home and your school, followed by specifications of several subway lines. Each subway line consists of the non-negative integer x,y coordinates of each stop on the line, in order. You may assume the subway runs in a straight line between adjacent stops, and the coordinates represent an integral number of metres. Each line has at least two stops. The end of each subway line is followed by the dummy coordinate pair -1,-1. In total there are at most 200 subway stops in the city.
Output

Output is the number of minutes it will take you to get to school, rounded to the nearest minute, taking the fastest route.
Sample Input

```
0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1 
```

Sample Output

```
21 
```
Source

Waterloo local 2001.09.22

The Algorithm and Specifications

Although at first the problem seems like the shortest path from two corners in a gargantuan grid, it eventually reduces to only the 200 subway stations because they are the only vertexes "special locations" that we care about. Hence, this is reduced to the shortest path on a 202-vertex graph (+2 for home and school points), where each vertex is identified by a number from 0 to 201 inclusive that represents the x and y locations of the vertex. Then, the respective weight of any two vertexes with locations x1, y1, x2 and y2 is the amount of minutes it takes to walk from (x1, y1) to (x2,y2), equivalent to the expression  sqrt((x1-x2)^2 + (y1-y2)^2) (the distance in m)/100 (to km) /10 (at 10 km/h) \*60 (to minutes), or sqrt((x1-x2)^2 + (y1-y2)^2)\*3/50. However, the stops that are connected by subway need to be divided by 4 again, for the subway is 4 times as quick.


The simple and obvious method is to use SPFA on the undirected dense graph. It is dense because each node has exactly n-1 daughter nodes, making it an incredible wate of time to use a edge list (vector). Simple edge matrixes (2d arrays) work.The input is most complicated.


In the input, we must connect every vertex to every other point with the walking weight, and furthermore connect each subway stop to its previous stop IF AND ONLY IF it is NOT a terminal. Thus, we have to keep track of whether the previous input read was -1, -1. This has multiple solutions, the most clear being a boolean value keeping track of whether the input for a single line ended or not.

Other than these, the problem is mostly transparent.

The Code Itself

#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

 struct stop
{
    int x,y;
} stops[205];
double map[205][205],dist[205];
int queue[1000000];
bool in[205];
int vtxs;
void spfa()
{
    memset(dist,127, sizeof dist );
    dist[0]=0.0;
    int h=0,t=0;
    queue[t++]=0;
    in[0]=true;
    while(h!=t)
    {
        int pop=queue[h++];
        for(int i=0;i<vtxs;i++)
        {
            if(i==pop)
                continue;
            if(dist[i]>dist[pop]+map[i][pop])
            {
                dist[i]=dist[pop]+map[i][pop];

                 if(!in[i])
                {
                    queue[t++]=i;
                    in[i]=true;
                }
            }
        }
        in[pop]=false;
    }
}

 int main()
{
    for (int i=0;i<204;i++)
        for (int j=0;j<204;j++)
            map[i][j]=map[j][i]=((i==j)?0.00:1000000.00);
    //freopen("subway.in","r",stdin);
    //freopen("subway.out","w",stdout);
    scanf("%d %d %d %d ",&stops[0].x,&stops[0].y,&stops[1].x,&stops[1].y);
    int i=0,ind=1;
    double tent = sqrt(double((stops[i].x-stops[ind].x))*\
                       double((stops[i].x-stops[ind].x))+\
                       double((stops[i].y-stops[ind].y))*\
                       double((stops[i].y-stops[ind].y)))/500.0*3.0;
    //map[i][ind]=(map[i][ind]>tent)?tent:map[i][ind];
    map[ind][i]=map[i][ind]=tent;
    int x,y;
    ind++;
    bool nr=true;
    while(scanf("%d %d",&x,&y)!=EOF)
    {
        if(x==-1 && y==-1)
        {
            nr=true;
            continue;
        }
        stops[ind].x=x;stops[ind].y=y;
        for(int i=0;i<ind;i++)
        {
            double tent = sqrt(double((stops[i].x-stops[ind].x))*\
                               double((stops[i].x-stops[ind].x))+\
                               double((stops[i].y-stops[ind].y))*\
                               double((stops[i].y-stops[ind].y)))/500.0*3.0;
            //map[i][ind]=(map[i][ind]>tent)?tent:map[i][ind];
            map[ind][i]=map[i][ind]=tent;
        }
        if(nr)
            nr=!nr;
        else
        {
            double tent = sqrt(double((stops[ind].x-stops[ind-1].x))*\
                               double((stops[ind].x-stops[ind-1].x))+\
                               double((stops[ind].y-stops[ind-1].y))*\
                               double((stops[ind].y-stops[ind-1].y)))/2000.0*3.0;
            map[ind-1][ind]=map[ind][ind-1]=tent;
        }
        ind++;
    }
    vtxs=ind;
    spfa();
    printf("%d",(int)(dist[1]+0.5));
}

Comments

Post a Comment

Popular posts from this blog

USACO Training "subset": Subset Sums

-
USACO Training "subset": Subset Sums Problem Statement Subset Sums JRM For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical. For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical: {3} and {1,2} This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions). If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum: {1,6,7} and {2,3,4,5} {2,5,7} and {1,3,4,6} {3,4,7} and {1,2,5,6} {1,2,4,7} and {3,5,6} Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways. Your program must calculate the answer, not look it up from a table. PROGRAM NAME: s
Read more

USACO 2018 Open: Talent Show

-
Image
USACO 2018 Open Talent Show In Short Given N objects with value Vi and weight Wi, a collection of elements is said to have total value-to-weight ratio as (the sum of their value) divided by (the sum of their weight). Find the best possible value-to-weight ratio of these X objects, given the restraint that the collection must have total weight at least W. Return that ratio multiplied by 1000 and floored. Analysis It would be very difficult to calculate this optimal ratio - we'd have to either try all possible collections - O(2^n), where n is at most 250, about 10 to the power of 75 calculations, OR use a greedy heuristic - get the objects with the best ratio until it satisfies the weight limit. Neither of those are too to our liking, so how about searching for it? The search space is linear and not infinite - it asks for the ratio to the closest thousandths. The search space is sorted as well - if ratio X is achievable, then ratio Y < X is also achievable, if
Read more

OpenJudge 1768: Kadane's Algorithm on 2D Arrays

-
OpenJudge 1768: Kadane's Algorithm on 2-D Arrays Simple Version Given a 2-D matrix of integers, find the sub-matrix of this whose sum is maximized, and find that sum. The size of the matrix is no larger than 100 by 100. Analysis O(N^4) - Works, but naive     That's true, an naive O(N^4) version would work. We simply need to calculate (two dimensional!) prefix sums first. A quick review to what 2-D prefix sums are:     The 2-D prefix sum of two coordinates, X and Y, is the sum of all elements that have X-coordinate less than or equal to X, and Y coordinate less than or equal to Y.     It can be calculated through tabulation by removing overlapping areas.     Let P be the prefix sum array and V be the array of values, so the formula is as follows:     P[x, y] = V[x, y] - P[x-1, y] - P[x, y-1] + P[x-1, y-1].     We need to add the P[x-1, y-1] at the end since subtracting P[x-1, y] and P[x, y-1] we had overlapped the P[x-1, y-1]. Then, all we need to
Read more