Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2230
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2230
Toll
By OBI - Olimpíada Brasileira de Informática 2002 
Brazil
Timelimit: 1
The prize for first place in the Brazilian Olympiad of Informatics, Juquinha and his family have won a one week trip to South Korea. As the country is stunning, with traditions, culture, very different architecture and cuisine of Brazil, the father of Juquinha Mr. Juca, decided to rent a car to explore the country. The roads are well maintained; all are two-way, and two cities can be directly connected by more than one road. However, on all roads you pay a fixed amount of toll (there is a toll each way between two cities). As Mr. Juca does not have much money to spend, travel with the car should be very thoughtful.
Write a program that known cities and existing roads in the country and the city where Juquinha and your family are, find each city (not the city where they are) that can be visited by them, given the restriction that Mr . Juca want to pay at most P tolls (considering only the outward journey).
Input
The input consists of several test sets. The first line of a test set contains four integers C (0 ≤ C ≤ 50), E (0 ≤ E ≤ 2500), L (0 ≤ L ≤ C) e P (0 ≤ P ≤ C). The values C e E respectively indicate the number of cities and the number of roads. Cities are identified by integers from 1 to C. the values L e P indicate, respectively, the city where the Juquinha family is at the time and the maximum number of tolls that Mr. Juca is willing to pay. At E following lines each one contains information of a road represented by a pair of positive integers X e Y (1 ≤ X,Y ≤ C), indicating that there is a road (two-way) of the city X to the city Y. The end of the input is indicated by C = E = L = P = 0.
Output
For each entry test set your program should produce three lines in the output. The first line should contain a test set identifier in the format "Teste n", where n is numbered from 1. In the second line should appear the identifiers of the cities that can be reached, in ascending order, separated by at least a blank. The third line should be left blank. The spelling shown in Example output below should be followed strictly.
| Input Sample | Output Sample |
|
5 4 2 1 1 2 2 3 3 4 4 5 9 12 1 2 2 1 1 5 2 1 3 2 9 3 3 4 4 8 4 7 7 6 5 6 4 5 3 7 0 0 0 0 |
Teste 1 1 3 Teste 2 2 3 4 5 6 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <queue>
#include <vector >
#define MAXN 10010
#define MP make_pair
#define LIMIT 99999
using namespace std;
typedef pair < int, int> ii;
vector<int> grafo[MAXN];
int visitado[MAXN], distancias[MAXN];
int main() {
int vertices, arestas, cidade, preco, teste = 1;
while (scanf("%d %d %d %d", &vertices, &arestas, &cidade, &preco) &&
(vertices || cidade || arestas || preco)) {
printf("Teste %d\n", teste++);
for (int i = 1; i < = vertices; i++) {
grafo[i].clear();
visitado[i] = 0;
distancias[i] = LIMIT;
}
for (int i = 0; i < arestas; i++) {
int u, v;
scanf("%d %d", &u, &v);
grafo[u].push_back(v);
grafo[v].push_back(u);
}
queue < ii> bfs;
bfs.push(MP(cidade, 0));
while (!bfs.empty()) {
ii davez = bfs.front();
bfs.pop();
int u = davez.first, d = davez.second;
if (visitado[u]) continue;
distancias[u] = d;
visitado[u] = 1;
for (int i = 0; i < int(grafo[u].size()); i++)
bfs.push(MP(grafo[u][i], d + 1));
}
distancias[cidade] = LIMIT;
for (int i = 1; i < = vertices; i++)
if (distancias[i] <= preco) printf("%d ", i);
printf("\n\n");
}
return 0;
}