10801 - Lift Hopping

[brianfry713]

20 seconds riding the first elevator.
http://www.uvatoolkit.com/problemssolve.php

[Muftee_Ruet]

Try these case:

INPUT

Code: Select all

3 2
100 5 3
0 1 2
1 2
1 2

3 2
100 5 3
0 1 2
0 1
1 2

OUTPUT

Code: Select all

163
68

[afruizc]

The key to solve this problem is to model the graph successfully I think that's what I'm lacking, because I keep getting WA. Here is the idea I used: I associate a number to every floor depending on the elevator that goes over that floor. For the first elevator I give the floors numbers from 0 to 99, for the second one from 100 to 199 and so on, so the floors traversed by the fifth elevator are numbered from 400 to 499. So far there is just half of the problem solved. After this, I need to work around the issue of elevators that stop at the same floor (this part is very likely to contain mu bug). I used an array (prev) to store wether another elevator stops at floor i or not. If prev == -1, it means that no elevator so far stops at floor i, otherwise, prev contains the number of the previous floor (remember, from 0 to 499). At this point, the graph is built, so I run Dijkstra's and print the solution.

Here is my code:

Code: Select all

Cut after AC :)

Here is some I/O I've tested my program with:

Input:

Code: Select all

3 30
100 100 1
0 2 4 5 6 7 8 21 22 23 24 25 26 30
1 2 19 11 12 13 14 15 16 30
1 10 30
2 99
100 1
0 1 98 99
1 98
3 1
100 10 100
0 1
0 1
0 1
2 5
1 1
0 3
4 5
4 89
7 2 4 8
3 34 45 56 77
4 23 34 89
0 99
3 99
5 99
12 90 34 56 22
0 4 7 3 6 8 98
4 10 20 23 46 50 69 88 99
0 3 12 45 50 77 88 99
0 20 46 77 98
0 50
2 99
10 40
1 2 3 4 99 0 12 
3 4 2 0 12 99
2 2
10 5
0 1 2
1 2
3 2
100 5 3
0 1 2
1 2
1 2
3 2
100 5 3
0 1 2
0 1
1 2
2 90
1 10
0 80
80 90

Output:

Code: Select all

449
417
10
IMPOSSIBLE
1671
2826
990
20
165
68
240

[brianfry713]

line 9 of the output should be 163 not 165.

Try rewriting your code in a more straightforward way. In my AC code, I use a priority_queue with a struct containing the elevator number, current floor, and time. I also have a min_time[5][100] array initialized to infinity. Then insert into the priority_queue each elevator that stops at floor 0. In the Dijkstra while loop, see if the entry at the top of the priority_queue can get to another floor at an earlier time, and try switching elevators at the current floor.

[afruizc]

Thanks brianfry713, I did as you said and get AC. It was my first time coding Dijkstra that way, but it is indeed less error prone. Thanks for your help .
For those who are still stuck, here are some test cases:

Input:

Code: Select all

3 30
100 100 1
0 2 4 5 6 7 8 21 22 23 24 25 26 30
1 2 11 12 13 14 15 16 19 30
1 10 30
2 99
100 1
0 1 98 99
1 98
3 1
100 10 100
0 1
0 1
0 1
2 5
1 1
0 3
4 5
4 89
7 2 4 8
3 34 45 56 77
4 23 34 89
0 99
3 99
5 99
12 90 34 56 22
0 3 4 6 7 8 98
4 10 20 23 46 50 69 88 99
0 3 12 45 50 77 88 99
0 20 46 77 98
0 50
2 99
10 40
0 1 2 3 4 12 99
0 2 3 4 12 99
2 2
10 5
0 1 2
1 2
3 2
100 5 3
0 1 2
1 2
1 2
3 2
100 5 3
0 1 2
0 1
1 2
2 90
1 10
0 80
80 90

Output:

Code: Select all

449
417
10
IMPOSSIBLE
1671
2826
990
20
163
68
240

[hpjhc]

Code: Select all

delete after AC

[uDebug]

What's wrong with my code, why complile error?

What's the compiler error you're getting?

Also, try submitting your code again. Looks like there might have been some minor issues with the judge earlier.

Finally, try changing the array called "time" (on Line #29) to something else. The word "time" may be a keyword.

[nbacool2]

Hi, guys. For some reason on the test cases my code produces 90% right answers and on the rest 10% it gives a lower answer than the correct one. I'm using Dijkstra's algorithm. I construct the graph by pairing each elevator's reachable floors with eacho ther and also keep for each edge which elevator we're using.
So in the priority Q I also keep for the current edge the elevator with which we are reaching the current floor and when I explore the children of the current floor I add 60 second extra time if the elevator we're using from the current floor to its child is different from the elevator that was stored in the priority queue. Any ideas what could be wrong?

Code: Select all

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <stack>
#include <utility>
#include <cmath>
#include <sstream>
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
const int MAXN = 100;
int elevatorCost[6];
vector<int> floorsForElevator[6];
int N, K;
vector<iii> G[MAXN];
int dist[MAXN];
vector<int> answers;
void read()
{
    memset(dist, 127, sizeof dist);
    for(int i = 0; i < MAXN; ++i) G[i].clear();
    for(int i = 0; i < 6; ++i) floorsForElevator[i].clear();
    //all set
    for(int i = 0; i < N; ++i)
    {
        cin >> elevatorCost[i];
    }
    string emptyStr;
    getline(cin, emptyStr);
    for(int i = 0; i < N; ++i)
    {
        string line;
        getline(cin, line);
        istringstream iss(line);
        int floor;
        while(iss >> floor)
        {
            floorsForElevator[i].push_back(floor);
        }
    }
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < floorsForElevator[i].size(); ++j)
        {
            for(int k = j+1; k < floorsForElevator[i].size(); ++k)
            {
                int f1 = floorsForElevator[i][j];
                int f2 = floorsForElevator[i][k];
                int cost = elevatorCost[i]*(abs(f1-f2));
                G[f1].push_back(iii(cost, ii(f2, i)));
                G[f2].push_back(iii(cost, ii(f1, i)));
            }
        }
    }
    //now run Dijkstra
    priority_queue<iii> Q;
    Q.push(iii(0, ii(0, -1)));
    dist[0] = 0;
    while(!Q.empty())
    {
        iii triple = Q.top(); Q.pop();
        int current = triple.second.first;
        int currentElevator = triple.second.second;
        for(int i = 0; i < G[current].size(); ++i)
        {
            int child = G[current][i].second.first;
            int childElevator = G[current][i].second.second;
            int cost = G[current][i].first;
            if(currentElevator != childElevator && currentElevator != -1) cost += 60;

            if(dist[current] + cost <= dist[child])
            {
                dist[child] = dist[current] + cost;
                Q.push(iii(-dist[child], ii(child, childElevator)));
            }
        }
    }
    if(dist[K] > (1 << 20)) answers.push_back(-1);
    else answers.push_back(dist[K]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    while(cin >> N)
    {
        cin >> K;
        read();
    }
    for(int i = 0; i < answers.size(); ++i)
    {
        //cout<<"CASE: "<<i<<endl;
        if(answers[i] == -1) cout<<"IMPOSSIBLE";
        else cout<<answers[i];
        cout<<'\n';
    }
    return 0;
}

[brianfry713]

For input:

Code: Select all

2 99
100 1
0 1 98 99
1 98

Your code is printing 357 instead of 417, so you are probably not adding 60 for one of the times you switch elevators. Try adding in temporary debug print statements in your code and go step by step to try to figure out where your issue is.

[kokx]

Hi Everyone. For some reason, my code is working perfectly on all inputs given here (as in, gives the same output as udebug and as told here). However, I still get WA. Does anyone know what is wrong?

https://gist.github.com/kokx/e55475fce0bc835bdf45

I've also added my entire input file and output for convenience.

So, does anyone have an idea what is wrong with my code? Or some more tricky inputs?

[brianfry713]

If k = 0 print 0.

[hquilo]

Hi,

It seems like the judge input does not have test cases in which no elevator stops at floor 0. Given this, for a test case such as (posted previously in this thread)

Code: Select all

2 99
10 40
1 2 3 4 99 0 12
3 4 2 0 12 99

it is OK to output

Code: Select all

IMPOSSIBLE