URAL 1434. Buses in Vasyuki

Author: 2015-08-27

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1434

1434. Buses in Vasyuki

Time limit: 3.0 second
Memory limit: 64 MB
The Vasyuki University is holding an ACM contest. In order to help the participants make their stay in the town more comfortable, the organizers composed a scheme of Vasyuki’s bus routes and attached it to the invitations together with other useful information.
The Petyuki University is also presented at the contest, but the funding of its team is rather limited. For the sake of economy, the Petyuki students decided to travel between different locations in Vasyuki using the most economical itineraries. They know that buses are the only kind of public transportation in Vasyuki. The price of a ticket is the same for all routes and equals one rouble regardless of the number of stops on the way. If a passenger changes buses, then he or she must buy a new ticket. And the Petyuki students are too lazy to walk. Anyway, it easier for them to write one more program than to walk an extra kilometer. At least, it’s quicker.
And what about you? How long will it take you to write a program that determines the most economical itinerary between two bus stops?
P.S. It takes approximately 12 minutes to walk one kilometer.

Input

The first input line contains two numbers: the number of bus routes in Vasyuki N and the total number of bus stops M. The bus stops are assigned numbers from 1 to M. The following N lines contain descriptions of the routes. Each of these lines starts with the number k of stops of the corresponding route, and then k numbers indicating the stops are given ( 1 ≤ N ≤ 1000, 1≤ M ≤ 105, there are in total not more than 200000 numbers in the N lines describing the routes). In the N+2nd line, the numbers A and B of the first and the last stops of the required itinerary are given (numbers A and B are never equal).

Output

If it is impossible to travel from A to B, then output −1. Otherwise, in the first line you should output the minimal amount of money (in roubles) needed for a one-person travel from A to B, and in the second line you should describe one of the most economical routes giving the list of stops where a passenger should change buses (including the stops A and B).

Sample

input output 
3 10
5 2 4 6 8 10
3 3 6 9
2 5 10
5 9
 
3
5 10 6 9
Problem Author: Eugine Krokhalev, Ekaterina Vasilyeva
Problem Source: The 7th USU Open Personal Contest – February 25, 2006

2. 思路

有若干条公交线路，给出每条线路上的站点，求从指定站点到另一指定站点的乘车方式，使得换乘次数最少。
从起点开始BFS，对某一站点，如果可以换乘，且能换乘的路线还没有乘坐过，则将该线路上的所有站点入队。在队列中使用一个标记CHANGE_BUS来记录换乘次数。

3.代码

#include <stdio.h>
#include <set>
#include <queue>

using namespace std;

#define MAX_N 1000
#define MAX_M 100000
#define CHANGE_BUS -1

void solveE5f_BusesInVasyuki();
void inputTransport(set<int> transport[], int routeNum);

int main() {
	solveE5f_BusesInVasyuki();
	return 0;
}

set<int> transport[MAX_N];
queue<int> q;
bool visitedStop[MAX_M], visitedRoute[MAX_N];
int pre[MAX_M], path[MAX_N];
void solveE5f_BusesInVasyuki() {
	int n, m, src, dest;
	scanf("%d %d", &n, &m);
	inputTransport(transport, n);
	scanf("%d %d", &src, &dest);

	q.push(src);
	pre[src] = -1;
	visitedStop[src] = true;
	q.push(CHANGE_BUS);
	int curr, fee = 0;
	bool found = false;
	while (!q.empty()) {
		curr = q.front();
		q.pop();

		if (curr == dest) {
			found = true;
			break;
		} else if (curr == CHANGE_BUS) {
			if (q.empty()) {
				break;
			}
			else {
				++fee;
				q.push(CHANGE_BUS);
				continue;
			}			
		}

		for (int i = 0; i < n; ++i) {
			if (!visitedRoute[i]) {
				set<int>::iterator it = transport[i].find(curr);
				if (it != transport[i].end()) {
					for (std::set<int>::iterator it2 = transport[i].begin(); it2 != transport[i].end(); ++it2) {
						if (!visitedStop[*it2]) {
							q.push(*it2);
							pre[*it2] = curr;
							visitedStop[*it2] = true;
						}
					}
					visitedRoute[i] = true;
				}
			}
		}
	}
	if (found) {
		printf("%d\n", fee);
	} else {
		printf("-1\n");
		return;
	}
	int cnt = 0;
	for (int i = dest; i != -1; i = pre[i]) {
		path[cnt++] = i;
	}

	for (int i = cnt - 1; i >= 0; --i) {
		printf("%d ", path[i]);
	}
	printf("\n");
}

void inputTransport(set<int> transport[], int routeNum) {
	int stopNum, stopId;
	for (int i = 0; i < routeNum; ++i) {
		scanf("%d", &stopNum);
		for (int j = 0; j < stopNum; ++j) {
			scanf("%d", &stopId);
			transport[i].insert(stopId);
		}
	}
}