Algoritmo de Bellman-Ford
É um pouco mais lento que dijkstra, mas é mais simples e fácil de compreender e permite pesos negativos nas arestas,
enquanto que dijkstra não permite.
#include <iostream>
#define INFINITY 99999999
using namespace std;
typedef struct {
int source;
int dest;
int weight;
} Edge; // Arestas
void BellmanFord(Edge edges[], int edgecount, int nodecount, int source) {
int i,j;
int *distance = new int [nodecount];
for (i = 0; i < nodecount; i++) {
distance[i] = INFINITY;
}
distance[source] = 0;
for (i = 0; i < nodecount; i++) {
// como otimizar este laço?
for (j = 0; j < edgecount; j++) {
if (distance[edges[j].dest] > distance[edges[j].source] + edges[j].weight) {
distance[edges[j].dest] = distance[edges[j].source] + edges[j].weight;
}
}
}
for (i = 0; i < edgecount; i++) {
if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) {
cout << "Ciclo negativo de pesos de arestas detectado" << endl;
break;
}
}
for (i = 0; i < nodecount; i++) {
cout << "Distancia menor entre nodos " << source << " e " << i <<" eh " << distance[i] << endl;
}
delete distance;
}
int main (void){
Edge Arestas[100];
int casos,nc,vertices,arestas;
cin >> casos;
for (nc = 0; nc < casos; nc ++){
cin >> vertices; //m
cin >> arestas;
for (int i=0; i< arestas; i++){
cin >> Arestas[i].source;
cin >> Arestas[i].dest;
cin >> Arestas[i].weight;
}
BellmanFord(Arestas,arestas,vertices,0); //Arestas,n de arestas,n de vertices,origem);
cout << endl;
}
return(0);
}
Entrada:
2
3 3
0 1 1000
1 2 15
2 1 -42
4 4
0 1 10
1 2 20
2 3 30
3 0 -60
Saída:
Ciclo negativo de pesos de arestas detectado
A distancia mais curta entre os nodos 0 e 0 eh 0
A distancia mais curta entre os nodos 0 e 1 eh 919
A distancia mais curta entre os nodos 0 e 2 eh 961
A
A
A
A
distancia
distancia
distancia
distancia
mais
mais
mais
mais
curta
curta
curta
curta
entre
entre
entre
entre
os
os
os
os
nodos
nodos
nodos
nodos
0
0
0
0
e
e
e
e
0
1
2
3
eh
eh
eh
eh
0
10
30
60
Análise do algoritmo
Edge Arestas[100];
typedef struct {
int source;
int dest;
int weight;
} Edge; // Arestas
2
1
2
12
3
1
3
8
4
2
0
-5
5
2
3
124
6
3
4
61
7
3
6
13
8
4
0
78
9
4
5
14
10
5
1
-3
11
6
4
4
2
0
1
2
3
4
5
6
0
α
α
α
α
α
α
(distance[1] > distance[0] + 31) ?
α > 0 + 31 ? (sim)
distance[1] = 31
0
1
2
3
4
5
6
0
31
α
α
α
α
α
(distance[4] > distance[0] + 78) ?
α > 0 + 31 ? (sim)
distance[4] = 78
distance [ ]
0
1
2
3
4
5
6
0
31
α
α
78
α
α
(distance[2] > distance[1] + 12) ?
α > 31 12
distance[2]= 43
...
0
1
2
3
4
5
6
0
31
43
39
56
70
52
curta
curta
curta
curta
curta
curta
curta
entre
entre
entre
entre
entre
entre
entre
distance [ ]
A
A
A
A
A
A
A
distancia
distancia
distancia
distancia
distancia
distancia
distancia
mais
mais
mais
mais
mais
mais
mais
os
os
os
os
os
os
os
nodos
nodos
nodos
nodos
nodos
nodos
nodos
0
0
0
0
0
0
0
4
6
Pega campo dest do vetor de Arestas (arestas[] .dest)
distance [ ]
5
61
3
i distance[i]
distance [ ]
1
12
14
78
8
31
4
4
1
0
-3
0
1
31
78
0
0
13
weight
4
dest
12
source
-5
Arestas[ ]
e
e
e
e
e
e
e
0
1
2
3
4
5
6
eh
eh
eh
eh
eh
eh
eh
0
31
43
39
56
70
52
Problemas envolvendo Bellman-Ford
UVA 11492 - Babel – Facilitado (ignore restrições)
sub-regional Brasil de 20 de setembro de 2008 - Problema B
Joaozinho e Mariazinha são dois irmãos que estão muito empolgados com suas aulas de idiomas, cada um está fazendo vários
diferentes cursinhos. Ao chegar em casa comentam sobre gramática, vocabulário, cultura dos países etc. Numa dessas
conversas perceberam que algumas palavras são comuns a mais de um idioma, mesmo que não necessariamente tenham o
mesmo significado. Por exemplo, “amigo” existe em português e espanhol e tem o mesmo significado, enquanto que “date” é
uma palavra comum entre francês e inglês mas que pode ter significados diferentes, uma vez que “date” também se refere a um
encontro em inglês, além de “data” de calendário. Já “red” em espanhol se refere a uma rede, enquanto que em inglês se refere
à corvermelha. Outro exemplo seria “actual” que, em inglês significa algo real e, em espanhol, tem o significado de presente,
atual (como em português).
Empolgados com essas descobertas, resolveram escrever num caderno todas as palavras em comum que conseguiram pensar,
associando cada uma a um par de idiomas. Observador como é, Joãozinho propôs um desafio a Mariazinha: dados um idioma
de origem e um de destino, escrever uma série de palavras sendo que a primeira necessariamente deveria pertencer ao idioma
de origem e a ´ultima ao de destino. Duas palavras adjacentes nessa seq¨uência deveriam necessariamente pertencer a um
mesmo idioma. Por exemplo, se o idioma de origem fosse português e o de destino francês, Mariazinha poderia escrever a
seq¨uência amigo actual date (português/espanhol, espanhol/inglês, inglês/francês).
Restrições: Mariazinha deve encontrar a solução que tenha o menor comprimento da seqüência total não contando os
espaços entre as palavras e duas palavras consecutivas não podem ter a mesma letra inicial.
Sendo assim, a solução anterior passa a ser inválida, pois “amigo” e “actual” têm a mesma letra inicial. é possível, porém,
encontrar outra solução, que no caso seria amigo red date, cujo comprimento total é 12. Joãozinho fez uma extensa pesquisa na
internet e compilou uma enorme lista de palavras e desafiou Mariazinha a resolver o problema. Como é possível que haja mais
de uma solução, ele pediu para que ela apenas respondesse o comprimento da seqüência encontrada dadas as restrições ou se
não há solução possível. Você seria capaz de ajudar Mariazinha?
Entrada
A entrada contém vários casos de teste. A primeira linha de um caso de teste contém um inteiro M (1 <= M < 2000),
representando o total de palavras compiladas por Joãozinho. A segunda linha contém duas cadeias de caracteres distintas O e
D, separadas por um espaço em branco, indicando os idiomas de origem e destino respectivamente. Cada uma das M linhas
seguintes contém três cadeias de caracteres I1, I2 e P, separadas por um espaço em branco, representando dois idiomas e uma
palavra comum entre ambos (I1 e I2 são sempre diferentes). Todas as cadeias de caracteres terão tamanho mínimo 1 e máximo
50 e conterão apenas letras minúsculas. Um mesmo par de idiomas pode ter várias palavras diferentes associadas a ele,
porém uma mesma palavra P nunca será repetida. O final da entrada é indicado por uma linha que contém apenas um zero.
Saída
Para cada caso de teste da entrada seu programa deve imprimir um único inteiro, o comprimento da menor seqüência que
satisfaça as restrições de Joãozinho, ou impossivel (em minúsculas, sem acento) caso não seja possível.
Exemplo de Entrada
4
portugues frances
ingles espanhol red
espanhol portugues amigo
frances ingles date
espanhol ingles actual
4
portugues alemao
ingles espanhol red
espanhol portugues amigo
frances ingles date
espanhol ingles actual
6
portugues frances
ingles espanhol red
espanhol portugues amigo
frances ingles date
frances espanhol la
portugues ingles a
espanhol ingles actual
0
Saída correspondente
12
impossivel
5
Resolução
Inicialmente, deve-se entender a entrada como um grafo. Pense que as duas palavras iniciais são origem e destino e a palavra
em comum entre as 2 línguas é a forma de transporte entre a origem e destino. O custo total de transporte ( distância ) entre a
origem e o destino seria o tamanho da palavra em questão. Vamos supor que uma pessoa deseja ir de Gaurama até Cotegipe
utilizando os meios de transporte disponíveis, escolhendo a rota cujo tamanho do meio em questão seja o menor possível.
Exemplo:
gaurama
0
carro
van
Onibus
5
gaurama cotegipe
gaurama erechim onibus
gaurama erechim van
gaurama erechim carro
erechim cotegipe onibusleito
erechim cotegipe vanzinha
0
nha
2
vanzi
Onib
usle
ito
erechim
cotegipe
1
O principal aqui é fazer uma entrada de dados correta para grafos. Inicia-se com a leitura do vetor de arestas.
Arestas[6002]
source
dest
weight
0
0
2
onibus
1
2
0
onibus
2
0
2
van
3
2
0
van
4
0
2
carro
5
2
0
carro
6
2
1
onibusleito
7
1
2
onibusleito
8
2
1
vanzinha
9
1
2
vanzinha
A chave agora é como converter os nomes para números na leitura para armazenar no vetor de arestas (Edge)
int main (void){
Edge Arestas[6002];
int casos,nc,achou,cont,tamanhostring;
string origem,destino;
map <string,int> mapa;
cin >> casos;
while (casos!=0){
mapa.clear();
cin >>origem >> destino;
mapa["gaurama"] = 0;
mapa[origem]=0;
mapa["cotegipe"] = 1;
mapa[destino]=1;
tamanhostring=2;
cont = 0;
for (nc = 0; nc < casos; nc ++){
cin >> origem >> destino >> Arestas[cont].weight;
Arestas[cont+1].weight = Arestas[cont].weight;
if (mapa.find(origem)!=mapa.end()){ // encontrou
achou = mapa[origem];
achou = mapa[gaurama] = 0
} else {
mapa[destino]=tamanhostring;
achou=tamanhostring++;
}
Arestas[cont].source= ...
gaurama erechim onibus
...
Arestas[6002]
0
1
source
dest
0
weight
onibus
0
onibus
Obs.: o uso de maps dá um ganho de 500 % em performance comparando com uma matriz de strings na qual teríamos que
pesquisar a toda a matriz a cada entrada para ver se a cidade já existe ou não na matriz.
UVA 558 - Wormholes
In the year 2163, wormholes were discovered. A wormhole is a subspace tunnel through space and time connecting two star
systems. Wormholes have a few peculiar properties:
• Wormholes are one-way only.
• The time it takes to travel through a wormhole is negligible.
• A wormhole has two end points, each situated in a star system.
• A star system may have more than one wormhole end point within its boundaries.
• For some unknown reason, starting from our solar system, it is always possible to end up in any star system by
following a sequence of wormholes (maybe Earth is the centre of the universe).
• Between any pair of star systems, there is at most one wormhole in either direction.
• There are no wormholes with both end points in the same star system.
All wormholes have a constant time difference between their end points. For example, a specific wormhole may cause the
person travelling through it to end up 15 years in the future. Another wormhole may cause the person to end up 42 years in the
past.
A brilliant physicist, living on earth, wants to use wormholes to study the Big Bang. Since warp drive has not been invented
yet, it is not possible for her to travel from one star system to another one directly. This can be done using wormholes, of
course.
The scientist wants to reach a cycle of wormholes somewhere in the universe that causes her to end up in the past. By
travelling along this cycle a lot of times, the scientist is able to go back as far in time as necessary to reach the beginning of the
universe and see the Big Bang with her own eyes. Write a program to find out whether such a cycle exists.
Input
The input file starts with a line containing the number of cases c to be analysed. Each case starts with a line with two numbers
n and m . These indicate the number of star systems (1 <=n<=1000) and the number of wormholes ( 1 <=m<=2000) . The star
systems are numbered from 0 (our solar system) through n-1 . For each wormhole a line containing three integer numbers x, y
and t is given. These numbers indicate that this wormhole allows someone to travel from the star system numbered x to the star
system numbered y, thereby ending up t (-1000 <= t <= 1000) years in the future.
Output
The output consists of c lines, one line for each case, containing the word possible if it is indeed possible to go back in time
indefinitely, or not possible if this is not possible with the given set of star systems and wormholes.
Sample Input
2
33
0 1 1000
1 2 15
2 1 -42
44
0 1 10
1 2 20
2 3 30
3 0 -60
Sample Output
possible
not possible
UVA 11090 - Going in Cycle!!
You are given a weighted directed graph with n vertices and m edges. Each cycle in the graph has a weight, which equals to
sum of its edges. There are so many cycles in the graph with different weights. In this problem we want to find a cycle with the
minimum mean.
Input
The first line of input gives the number of cases, N. N test cases follow. Each one starts with two numbers n and m. m lines
follow, each has three positive number a, b, c which means there is an edge from vertex a to b with weight of c.
Output
For each test case output one line containing “Case #x: ” followed by a number that is the lowest mean cycle in graph with 2
digits after decimal place, if there is a cycle. Otherwise print “No cycle found.”.
Constraints
- n ≤ 50
- a, b ≤ n
- c ≤ 10000000
Sample Input
5
2 1
1 2 1
2 2
1 2 2
2 1 3
3 4
1 2 12
2 1 -2
2 3 5
3 2 -6
4 5
1 2 5
2 3 2
3 1 6
3 4 3
4 3 -8
4 6
1 2 1
2 3 8
2 4 6
4 3 -1
3 2 2
3 1 6
Sample Output
Case #1: No cycle found.
Case #2: 2.50
Case #3: -0.50
Case #4: -2.50
Case #5: 2.33
UVA 515 - King
Once, in one kingdom, there was a queen and that queen was expecting a baby. The queen prayed: ``If my child was a son and
if only he was a sound king.'' After nine months her child was born, and indeed, she gave birth to a nice son.
Unfortunately, as it used to happen in royal families, the son was a little retarded. After many years of study he was able just to
add integer numbers and to compare whether the result is greater or less than a given integer number. In addition, the numbers
had to be written in a sequence and he was able to sum just continuous subsequences of the sequence.
The old king was very unhappy of his son. But he was ready to make everything to enable his son to govern the kingdom after
his death. With regards to his son's skills he decided that every problem the king had to decide about had to be presented in a
form of a finite sequence of integer numbers and the decision about it would be done by stating an integer constraint (i.e. an
upper or lower limit) for the sum of that sequence. In this way there was at least some hope that his son would be able to make
some decisions.
After the old king died, the young king began to reign. But very soon, a lot of people became very unsatisfied with his
decisions and decided to dethrone him. They tried to do it by proving that his decisions were wrong.
Therefore some conspirators presented to the young king a set of problems that he had to decide about. The set of problems
was in the form of subsequences
of a sequence
. The king thought a
minute and then decided, i.e. he set for the sum
of each subsequence Si an integer constraint ki
(i.e
resp.) and declared these constraints as his
or
decisions.
After a while he realized that some of his decisions were wrong. He could not revoke the declared constraints but trying to save
himself he decided to fake the sequence that he was given. He ordered to his advisors to find such a sequence S that would
satisfy the constraints he set. Help the advisors of the king and write a program that decides whether such a sequence exists or
not.
Input
The input file consists of blocks of lines. Each block except the last corresponds to one set of problems and king's decisions
about them. In the first line of the block there are integers n, and m where 0 < n <=100 is length of the sequence S and 0 < m
<=100 is the number of subsequences Si. Next m lines contain particular decisions coded in the form of quadruples si, ni, oi, ki,
where oi represents operator > (coded as gt) or operator < (coded as lt) respectively. The symbols si, ni and ki have the meaning
described above. The last block consists of just one line containing 0.
Output
The output file contains the lines corresponding to the blocks in the input file. A line contains text successful conspiracy when
such a sequence does not exist. Otherwise it contains text lamentable kingdom. There is no line in the output file corresponding
to the last ``null'' block of the input file.
Sample Input
42
1 2 gt 0
2 2 lt 2
12
1 0 gt 0
1 0 lt 0
0
Sample Output
lamentable kingdom
successful conspiracy
UVA 10702 – Traveling Salesman!!
Jean is a travelling salesman. He keeps travelling among some cities. When he arrives in a city, he sells everything he has and
buy new things. Then he travels to another city, sells his items and buy new ones.
In this problem you will have to find the total amount of money Jean will gain on the optimal tour. On a tour he can go to some
city more than once, and he must finish his tour in some cities. Also there is a starting city for his tour and the number of intercity travels he wants to do in his tour.
Input
The input file contains several input sets. The description of each set is given below:
Each set starts with four integers C (2 ≤ C ≤ 100), the number of cities, S (1 ≤ S ≤ 100), the identifier of the starting city, E (1
≤ E ≤ 100), the number of cities his tour can end at, and T (1 ≤ T ≤ 1000), the number of inter-city travels he wants to do.
Follow C lines with C non-negative integers. The j'th integer of the i'th line will describe the profit he earns when he goes from
city i to city j. As he does not want to make a trip to a city he is already, the i'th integer of the i'th line will always be 0. Note
that going from city i to city j can have a different profit than going from city j to city i.
After there will be a line with E integers, the identifier of the cities he can end his tour.
Input is terminated by a set where C=S=E=T=0. This set should not be processed. There is a blank line beteween two input
sets.
Output
For each input set produce one line of output, the total profit he can earn in the corresponding tour.
Sample Input
3122
035
501
920
23
0000
Sample Output
7
Algoritmo de Floyd - Warshall
#include <iostream>
#include <iomanip>
#define INFINITO 999999999
using namespace std;
/* A estrutura digraph representa um digrafo. O campo adj é um ponteiro
para a matriz de adjacência do digrafo. O campo Vertices contém o número de Vértices
e o campo A contém o número de arcos do digrafo. */
struct digraph {
int V;
int A;
int adj[301][301];
};
/* Um objeto do tipo Digraph contém o endereço de um digraph. */
typedef struct digraph *Digraph;
void Floyd (Digraph G) {
for (int k=1; k <= G->V; k++) {
for (int i=1; i <= G->V; i++) {
for (int j=1; j <= G->V; j++){
if ( (G->adj[j][k]+G->adj[k][i] < G->adj[j][i]) ) {
G->adj[j][i]=G->adj[j][k]+G->adj[k][i];
}
}
}
}
}
int main(void){
Digraph D= new (struct digraph);
int i, j, vertices, arestas, origem, destino, custo;
cin >> vertices >> arestas;
for (i=0; i<vertices+1; i++){
for (j=0; j<vertices+1; j++){
D->adj[i][j]=INFINITO;
}
}
D->V=vertices;
D->A=arestas;
for (i=0; i<arestas; i++){
cin >> origem >> destino >> custo;
D->adj[origem][destino]=custo;
}
Floyd (D);
for (i=1;i<D->V+1;i++){ // Mostra a Matriz de Adjascencia
for (j=1;j<D->V+1;j++)
cout << setw(12) << D->adj[i][j] << " " ;
cout << endl;
}
return(0);
}
floyd.in
4
1
3
1
2
2
4
3
7
3
1
2
1
4
2
4
5
4
8
10
12
6
3
UVA – 186 – Trip Routing
Your employer, the California Car Club (CCC), has decided to provide a trip routing service to its members. Your job is to
write a program which reads a list of departure point-destination point pairs and calculates the shortest routes between them.
For each trip, your program will print a report which itemises the names of each city passed through, with route names and leg
distances.
Input
Input to your program will be in two parts. The first part is a map in the form of a list of highway segments. Each segment is
designated by a line containing four fields which are separated by commas. The first two fields are 1-20 characters each, and
are the names of the cities which are at each end of the highway segment. The third field is the 1-10 character name of the
route. The fourth field is the number of miles between the two endpoints, expressed as a positive integer. The highway segment
list will be terminated by an empty line. The second part of the input is a list of departure point-destination point pairs, one per
line. The departure point is given first, followed by a comma and the destination point. Each of the cities is guaranteed to have
appeared in the first part of the input data, and there will be a path that connects them. The list is terminated by the end of file.
Output
The output should be a series of reports, one for each departure point-destination point pair in the input. Each report should be
in exactly the same form as those in the example below. There should be two blank lines before each report (including the
first one).
Sample input
San Luis Obispo,Bakersfield,CA-58,117
Bakersfield,Mojave,CA-58,65
Mojave,Barstow,CA-58,70
Barstow,Baker,I-15,62
Baker,Las Vegas,I-15,92
San Luis Obispo,Santa Barbara,US-101,106
San Luis Obispo,Santa Barbara,CA-1,113
Santa Barbara,Los Angeles,US-101,95
Bakersfield,Wheeler Ridge,CA-99,24
Wheeler Ridge,Los Angeles,I-5,88
Mojave,Los Angeles,CA-14,94
Los Angeles,San Bernardino,I-10,65
San Bernardino,Barstow,I-15,73
Los Angeles,San Diego,I-5,121
San Bernardino,San Diego,I-15,103
Santa Barbara,Las Vegas
San Diego,Los Angeles
San Luis Obispo,Los Angeles
Sample output
From
-------------------Santa Barbara
Los Angeles
San Bernardino
Barstow
Baker
To
-------------------Los Angeles
San Bernardino
Barstow
Baker
Las Vegas
Route
Miles
---------- ----US-101
95
I-10
65
I-15
73
I-15
62
I-15
92
----Total
387
From
To
Route
Miles
-------------------- -------------------- ---------- ----San Diego
Los Angeles
I-5
121
----Total
121
From
-------------------San Luis Obispo
Santa Barbara
To
-------------------Santa Barbara
Los Angeles
Route
Miles
---------- ----US-101
106
US-101
95
----Total
201
Note: There will be no extraneous blanks in the input. There will be no more than 100 cities in the map and no more than 200 highway
segments. The total distance in each best route is guaranteed to fit within a 16-bit integer.