1048 - Low Cost Air Travel

All about problems in Volume 10. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Lim.YuDe
New poster
Posts: 15
Joined: Sat Dec 13, 2014 1:32 pm

Re: 1048 - Low Cost Air Travel

Post by Lim.YuDe » Mon Mar 02, 2015 4:06 pm

I used dijkstra and stored the path history to get to each state (city, cost) in order to print the path.
I am getting correct output for my test cases including the given sample test cases, but TLE when submitting it to the judge :(
I think the TLE is not due to the algorithm but due to the way I store the path of tickets, but cannot find the problem.
Can anybody help?

My test input:

Code: Select all

3 
225 3 1 3 4 
200 2 1 2 
50 2 2 3 
1 
2 1 3 
3 
100 2 2 4 
100 3 1 4 3 
200 3 1 2 3 
2 
3 1 4 3 
3 1 2 4 
20
100 3 1 2 3
50 2 1 4
150 2 2 4
50 2 3 1
10 3 4 5 3
100 3 1 2 3
50 2 1 4
150 2 2 4
50 2 3 1
10 3 4 5 3
100 3 1 2 3
50 2 1 4
150 2 2 4
50 2 3 1
10 3 4 5 3
100 3 1 2 3
50 2 1 4
150 2 2 4
49 2 3 1
10 3 4 5 3
3
3 1 3 1
4 1 2 3 5
5 1 3 2 5 4
0
My test output:

Code: Select all

Case 1, Trip 1: Cost = 225
  Tickets used: 1
Case 2, Trip 1: Cost = 100
  Tickets used: 2
Case 2, Trip 2: Cost = 300
  Tickets used: 3 1
Case 3, Trip 1: Cost = 109
  Tickets used: 2 5 19
Case 3, Trip 2: Cost = 209
  Tickets used: 1 19 2 5
Case 3, Trip 3: Cost = 417
  Tickets used: 2 5 19 1 19 2 5 19 2
My code:

Code: Select all

#include <bits/stdc++.h>
using namespace std;

#define REP(i, a) for (int i = 0; i < a; i++)
#define REPP(i, a, b) for (int i = a; i < b; i++)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define INF 0x3f3f3f3f

int ntickets;
int price, ncities;
int city;
int nitineraries;

vi tickets[20]; // each ticket has a list of cities in order
int prices[20]; // each ticket's price
vi buy[200]; // index of tickets purchaseable at the city
vi itinerary;

map<int, int> id2idxmp; // city id to index map
map<ii, int> mp;

vi prevtickets; // prev tickets
vi bestidxs; // biggest indices

void addcity(int c) {
    if (id2idxmp.count(c)) return;

    int idx = id2idxmp.size();
    id2idxmp[c] = idx;
}

int index(int c) {
    return id2idxmp[c];
}

pair<int, ii> pp(int cost, int ticketidx, int neededidx) {
    return make_pair(cost, make_pair(ticketidx, neededidx));
}

pair<int, pair<ii, vi> > ppp(int cost, int ticketidx, int neededidx, vi &path) {
    return make_pair(cost, make_pair(make_pair(ticketidx, neededidx), path));
}

int dijkstra() {
    if (itinerary.size() < 2) return 0;

    prevtickets.clear();
    bestidxs.clear();
    mp.clear();

    vi path;
    int st = itinerary[0];
    set<pair<int, pair<ii, vi> > > ppq; // cost, ticketidx, neededidx, path
    set<pair<int, ii> > pq; // cost, ticketidx, neededidx
    REP(i, buy[st].size()) {
        int tic = buy[st][i];
        pq.insert( pp(prices[tic], tic, 1) );
    }

    int cost, ticketidx, neededidx, city, curneededidx;
    while (!pq.empty()) {
        set<pair<int, ii> >::iterator it = pq.begin();
        cost = it->first, ticketidx = it->second.first, neededidx = it->second.second;
        pq.erase(it);

        curneededidx = neededidx;
        REPP(i, 1, tickets[ticketidx].size()) {
            city = tickets[ticketidx][i];
            if (itinerary[curneededidx] == city) {
                curneededidx++;
            }
            if (!mp.count(make_pair(city, cost))) {
                prevtickets.push_back(ticketidx);
                bestidxs.push_back(curneededidx);
                mp[make_pair(city, cost)] = prevtickets.size()-1;
            } else if (bestidxs[mp[make_pair(city, cost)]] < curneededidx) {
                prevtickets[mp[make_pair(city, cost)]] = ticketidx;
                bestidxs[mp[make_pair(city, cost)]] = curneededidx;
            }
            if (curneededidx == itinerary.size()) {
                return cost;
            }
            REP(j, buy[city].size()) {
                int tic = buy[city][j];
                pq.insert( pp(cost + prices[tic], tic, curneededidx) );
            }
        }
    }

    return -1;
}

void printtickets(int st, int ed, int cost2) {
    if (cost2 <= 0) return;
    int tused = prevtickets[mp[make_pair(ed, cost2)]];
    int nexted = tickets[tused][0];
    int nextcost2 = cost2 - prices[tused];
    if (nextcost2 == 0) {
        printf("%d", tused+1);
        return;
    }
    printtickets(st, nexted, nextcost2);
    printf(" %d", tused+1);
}

int main() {
    int tc = 0;
    while (scanf("%d", &ntickets), ntickets) {
        tc++;
        id2idxmp.clear();
        REP(i, 200) buy[i].clear();

        REP(i, ntickets) {
            scanf("%d%d", &price, &ncities);
            prices[i] = price;
            tickets[i].clear();
            REP(j, ncities) {
                scanf("%d", &city);
                addcity(city);
                tickets[i].push_back(index(city));
                if (j == 0) buy[index(city)].push_back(i);
            }
        }

        scanf("%d", &nitineraries);
        REP(i, nitineraries) {
            itinerary.clear();
            scanf("%d", &ncities);
            REP(j, ncities) {
                scanf("%d", &city);
                addcity(city);
                itinerary.push_back(index(city));
            }
            int cost = dijkstra();
            printf("Case %d, Trip %d: Cost = %d\n", tc, i+1, cost);
            printf("  Tickets used: ");
            printtickets(itinerary[0], itinerary[itinerary.size()-1], cost);
            printf("\n");
        }
    }
    return 0;
}

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 1048 - Low Cost Air Travel

Post by dibery » Wed Mar 04, 2015 12:01 pm

I got

Code: Select all

Case 1, Trip 1: Cost = 225                
  Tickets used: 1                         
Case 2, Trip 1: Cost = 100                
  Tickets used: 2                         
Case 2, Trip 2: Cost = 300                
  Tickets used: 3 1                       
Case 3, Trip 1: Cost = 109                
  Tickets used: 17 20 19                  
Case 3, Trip 2: Cost = 209                
  Tickets used: 16 19 17 20               
Case 3, Trip 3: Cost = 417                
  Tickets used: 17 20 19 16 19 17 20 19 17
I think you should report the ticket ID, not the city ID.
Also, your input doesn't lead to unique solution.
In case 3, trip 2, the path can also be "1 19 17 20"
Life shouldn't be null.

Lim.YuDe
New poster
Posts: 15
Joined: Sat Dec 13, 2014 1:32 pm

Re: 1048 - Low Cost Air Travel

Post by Lim.YuDe » Fri Mar 06, 2015 3:39 pm

Thanks for your reply dibery.

My bad that the input doesn't lead to a unique solution.
However, I am printing the tickets; otherwise I would not be printing a 19 (no city has id 19 in case 3).

Would you happen to have any input? I would be much obliged. I've tried a few test cases but I can't seem to find what's wrong. (Can't find a way to TLE my solution)

Post Reply

Return to “Volume 10 (1000-1099)”