[URI ONLINE JUDGE] – 1328 – Go Easy

The mayor of a city wants to introduce a new transport system to simplify the life of its inhabitants. That will be done via the use of a debit card, which the mayor named “GoEasy”. There are two means of transportation in the city: trains and buses. The train system is “zone based” whereas the bus system is “journey based”. The fare for a journey is computed as follows:

  • There is an initial two money units fare for entering the transport system, regardless of the initial means of transportation.
  • When travelling by train a customer pays four money units for each change of zone.
  • When travelling by bus a customer pays one money unit each time she/he boards a bus.

A transport system map will provide information about the stations belonging to each zone, and the sequence of stations for each bus and train itinerary. Buses and trains move in both directions in each itinerary, and no train or bus goes through the same station twice during a single trip through an itinerary. It is always possible to go from any station to any other station using trains and/or buses. The rules for computing fares are strict: if during a train journey a customer enters a given zone twice, she/he is charged twice; similarly, if during a bus journey a customer boards twice the bus for the same itinerary, she/he is charged twice.

In the transport map above a customer can travel from station 2 to station 4 paying just two money units, by using line T1, since they are in the same zone. But if the customer needs to go from station 2 to 5, then the best is to take the bus B3 to station 10 and then take the bus B2 to station 5, paying in total four money units. Rather than tracking the whole trip of each passenger, the idea of the mayor is that machines will be placed in all stations, and travellers are supposed to swipe their personal GoEasy travel card only when starting AND finishing the whole journey. Since all the machines are interconnected into a network, based on the departure and arrival stations the system can compute the minimum cost possible for the trip, and that amount is charged from the traveller’s debit card. All that is missing is a computer system for doing the calculations for the fare to be deducted. So, given the map of the transport system in the city, you must write a program to compute the minimum fare the customer should pay to travel between two given stops/stations.

Input

The input contains several test cases. The first line of a test case contains two integers Z and S, which indicate respectively the number of zones (1 ≤ Z ≤ 30) and the number of train/bus stations in the city (1 ≤S ≤ 100). Each station has a unique identification number ranging from 1 to S, and each station belongs to exactly one zone. Each of the following Z lines describes the stations belonging to a zone. The description for a zone starts with an integer K indicating the number of stations (1 ≤ KS) in the zone, followed by Kintegers representing the stations in the zone. After that comes a line with two integer numbers T and B, representing respectively the number of train itineraries (1 ≤ T ≤ 50) and the number of bus itineraries (1 ≤B ≤ 50). Next comes T lines describing train itineraries, followed by B lines describing bus itineraries. The description of each itinerary consists of a line containing an integer L indicating the number of stations (2 ≤ LS) in the itinerary, followed by L integers specifying the sequence of stations in the itinerary. Finally it comes a line with two integers X and Y (1 ≤ XS, 1 ≤ YS and XY ), specifying that the customer travelled from station X to station Y . The end of input is indicated by Z = S = 0.

Output

For each test case your program should output one line, containing an integer representing the amount to be deducted from the traveller’s GoEasy card.

Sample Input Sample Output
3 15
2 8 9
7 2 3 4 7 12 13 14
6 1 5 6 10 11 15
3 3
5 1 2 3 4 5
3 1 6 11
4 4 8 12 11
6 2 7 12 13 14 15
3 5 10 15
6 1 2 3 8 9 10
11 6
3 15
2 8 9
7 2 3 4 7 12 13 14
6 1 5 6 10 11 15
3 3
5 1 2 3 4 5
3 1 6 11
4 4 8 12 11
6 2 7 12 13 14 15
3 5 10 15
6 1 2 3 8 9 10
11 5
0 0
2
4

 

my solution:

<br />// by David H Ng & Karry Smith
#include
#include
#include
#include
#include
#include
<map> #include </map>

using namespace std;

struct Station {
int zone;
vector<pair<int, int> > transports;

Station() : zone(-1),
transports(vector<pair<int, int> >()) { }
};

struct Transport {
char type;
vector itineraries;
};

struct Edge {
pair<int, int> to;
int cost;

Edge(pair<int, int> t, int c) : to(t), cost(c) { }
};

struct Node {
int distance, station, transport;
vector edges;
bool edgesCalculated;
pair<int, int> previous;

Node() : station(-1), transport(-1), distance(INT_MAX),
edges(vector()), edgesCalculated(false),
previous(pair<int, int>(-1, -1)) { }
Node(int st, int tr) : station(st), transport(tr),
distance(INT_MAX), edges(vector()), edgesCalculated(false),
previous(pair<int, int>(-1, -1)) { }
};

vector stations;
vector transports;
vector<vector > nodes;

struct NodeReference {
pair<int, int> pos;
int distance;

NodeReference(pair<int, int> p) : pos(p)
{
distance = nodes[pos.first][pos.second].distance;
}

bool operator<(const NodeReference other) const { return distance > other.distance;
}
};

void initNodes(int from, int to) {
nodes = vector<vector >(stations.size() + 2);

vector internal;
internal.push_back(Node(from, -1));
internal[0].distance = 2;
nodes[stations.size()] = internal;

internal[0] = Node(to, -1);
nodes[stations.size() + 1] = internal;

for(int i = 0; i < stations.size(); ++i) {
const Station& s = stations[i];

for(int j = 0; j < s.transports.size(); ++j) {
Node n(i, j);

if (i == from)
nodes[stations.size()][0].edges.push_back(Edge(pair<int, int>(i, j),
transports[s.transports[j].first].type == 'B' ? 1 : 0));
if (i == to)
n.edges.push_back(Edge(pair<int, int>(stations.size() + 1, 0), 0));

if (j >= nodes[i].size())
nodes[i].resize(j + 1);
nodes[i][j] = n;
}
}
}

int getMinPrice(int from, int to) {
initNodes(from, to);

vector heap;
vector<vector > visited(nodes.size());
for(int i = 0; i < nodes.size(); ++i) {
visited[i] = vector(nodes[i].size(), false);
}

heap.push_back(NodeReference(pair<int, int>(stations.size(), 0)));

while(!heap.empty()) {
pair<int, int> current = heap.front().pos;
Node& minNode = nodes[current.first][current.second];
pop_heap(heap.begin(), heap.end());
heap.pop_back();

if (visited[current.first][current.second])
continue;

if (current.first == stations.size() + 1)
break;

if (minNode.distance == INT_MAX)
break;

if (!minNode.edgesCalculated && current.first < stations.size()) {
static const int Offsets[] = { 1, -1 };

const Station& st = stations[minNode.station];
const pair<int, int>& p = st.transports[minNode.transport];
const Transport& t = transports[p.first];
int index = p.second;

// Nodes in station

int cost;
for(int i = 0; i < st.transports.size(); ++i) {
if (st.transports[i] == p)
continue;
cost = 0;
int nextIndex = st.transports[i].first;
const Transport& nextT = transports[nextIndex];
if (nextT.type == 'B')
cost = nextIndex == p.first ? 0 : 1;

minNode.edges.push_back(Edge(pair<int, int>(minNode.station, i), cost));
}

// Next stations using this transport
for(int j = 0; j < 2; ++j) {
if(index + Offsets[j] < 0 || index + Offsets[j] >= t.itineraries.size())
continue;

int nextStationIndex = t.itineraries[index + Offsets[j]];
const Station& nextStation = stations[nextStationIndex];

for(int k = 0; k < nextStation.transports.size(); ++k) {
int nextTransportIndex = nextStation.transports[k].first;
if (nextTransportIndex != p.first)
continue;
const Transport& nextTransport = transports[nextTransportIndex];

int cost = 0;
if(nextTransport.type == 'T')
cost = st.zone != nextStation.zone ? 4 : 0;

minNode.edges.push_back(Edge(pair<int, int>(nextStationIndex,
k), cost));
}
}

minNode.edgesCalculated = true;
}

for(int i = 0; i < minNode.edges.size(); ++i) {
int alt = minNode.distance + minNode.edges[i].cost;
Node& neighbour = nodes[minNode.edges[i].to.first][minNode.edges[i].to.second];

if (!visited[minNode.edges[i].to.first][minNode.edges[i].to.second] &&
alt < neighbour.distance) { neighbour.distance = alt; neighbour.previous = current; heap.push_back(NodeReference(minNode.edges[i].to)); push_heap(heap.begin(), heap.end()); } } visited[current.first][current.second] = true; } return nodes[stations.size() + 1][0].distance; } Transport readTransport() { int k; cin >> k;
vector itineraries(k);

for(int i = 0; i < k; ++i) { cin >> itineraries[i];
--itineraries[i];
}

Transport result;
result.itineraries = itineraries;

return result;
}

int main() {
int zoneCount, stationCount;

while(cin >> zoneCount >> stationCount &&
zoneCount > 0 && stationCount > 0) {
stations = vector(stationCount);

for(int i = 0; i < zoneCount; ++i) { int k; cin >> k;

for(int j = 0; j < k; ++j) { int value; cin >> value;
stations[value - 1].zone = i;
}
}

int trainCount, busCount;
cin >> trainCount >> busCount;

transports = vector(trainCount + busCount);
for(int i = 0; i < transports.size(); ++i) {
transports[i] = readTransport();
transports[i].type = i < trainCount ? 'T' : 'B';

for(int j = 0; j < transports[i].itineraries.size(); ++j) {
stations[transports[i].itineraries[j]]
.transports.push_back(pair<int, int>(i, j));
}
}

int from, to;
cin >> from >> to;

int result = getMinPrice(from - 1, to - 1);

cout << result << '\n';
}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s