## 1048 - Low Cost Air Travel

Moderator: Board moderators

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

### Re: 1048 - Low Cost Air Travel

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

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
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;
}
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, ntickets) {
scanf("%d%d", &price, &ncities);
prices[i] = price;
tickets[i].clear();
REP(j, ncities) {
scanf("%d", &city);
tickets[i].push_back(index(city));
}
}

scanf("%d", &nitineraries);
REP(i, nitineraries) {
itinerary.clear();
scanf("%d", &ncities);
REP(j, ncities) {
scanf("%d", &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

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.
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