Problema: 1148
Enunciado:
No ano 2050, após diversas tentativas da ONU de manter a paz no mundo, explode a terceira guerra mundial. Segredos industriais, comerciais e militares obrigaram todos os países a utilizar serviços de espionagem extremamente sofisticados, de forma que em cada cidade do mundo há ao menos um espião de cada país. Esses espiões precisam se comunicar com outros espiões, com informantes e mesmo com as suas centrais durante as suas ações. Infelizmente não existe uma forma segura de um espião se comunicar em um período de guerra, então as mensagens são sempre enviadas em código para que somente o destinatário consiga ler a mensagem e entender o seu significado.
Os espiões utilizam o unico serviço que funciona no período de guerra, os correios. Cada cidade possui uma agência postal onde as cartas são enviadas. As cartas podem ser enviadas diretamente ao seu destino ou a outras agências postais, até que a carta chegue à agência postal da cidade de destino, se isso for possível.
Uma agência postal na cidade A pode enviar diretamente uma carta impressa para a agência postal da cidade B se houver um acordo de envio de cartas, que determina o tempo, em horas, que uma carta leva para chegar da cidade A à cidade B (e não necessariamente o contrário). Se não houver um acordo entre as agências A e B, a agência A pode tentar enviar a carta a quantas agências for necessário para que a carta chegue ao seu destino, se isso for possível.
Algumas agências são interligadas por meios eletrônicos de comunicação, como satélites e fibras ópticas. Antes da guerra, essas ligações atingiam todas as agências, fazendo com que uma carta fosse enviada de forma instantânea, mas durante o período de hostilidades cada país passou a controlar a comunicação eletrônica e uma agência somente pode enviar uma carta a outra agência por meio eletrônico (ou seja, instantaneamente) se ela estiver no mesmo país. Duas agências, A e B, estão no mesmo país se houver uma forma de uma carta impressa enviada de uma das agências ser entregue na outra agência.
O serviço de espionagem do seu país conseguiu obter o conteúdo de todos os acordos de envios de mensagens existentes no mundo e deseja descobrir o tempo mínimo para se enviar uma carta entre diversos pares de cidades. Você seria capaz de ajudá-lo?
Os espiões utilizam o unico serviço que funciona no período de guerra, os correios. Cada cidade possui uma agência postal onde as cartas são enviadas. As cartas podem ser enviadas diretamente ao seu destino ou a outras agências postais, até que a carta chegue à agência postal da cidade de destino, se isso for possível.
Uma agência postal na cidade A pode enviar diretamente uma carta impressa para a agência postal da cidade B se houver um acordo de envio de cartas, que determina o tempo, em horas, que uma carta leva para chegar da cidade A à cidade B (e não necessariamente o contrário). Se não houver um acordo entre as agências A e B, a agência A pode tentar enviar a carta a quantas agências for necessário para que a carta chegue ao seu destino, se isso for possível.
Algumas agências são interligadas por meios eletrônicos de comunicação, como satélites e fibras ópticas. Antes da guerra, essas ligações atingiam todas as agências, fazendo com que uma carta fosse enviada de forma instantânea, mas durante o período de hostilidades cada país passou a controlar a comunicação eletrônica e uma agência somente pode enviar uma carta a outra agência por meio eletrônico (ou seja, instantaneamente) se ela estiver no mesmo país. Duas agências, A e B, estão no mesmo país se houver uma forma de uma carta impressa enviada de uma das agências ser entregue na outra agência.
O serviço de espionagem do seu país conseguiu obter o conteúdo de todos os acordos de envios de mensagens existentes no mundo e deseja descobrir o tempo mínimo para se enviar uma carta entre diversos pares de cidades. Você seria capaz de ajudá-lo?
Linguagem: C++
Neste problema foi utilizado o algoritmo de Floyd Warshall para resolver a solução.
Antes de aplicar o algoritmo, quando o grafo está sendo montado é verificado se há um caminho ligando o ponto a ao ponto b e também o ponto b ao ponto a, para quaisquer pontos a e b. Neste caso, é colocado a distancia 0 entre eles, visto que o problema permite deslocamento sem custo.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #include <iostream> #include <vector> using namespace std; vector< vector <int> > graph; #define INF 1000000 void floyd_warshall(){ int i, j, k; for (k = 0; k < graph.size(); k++) { for (i = 0; i < graph.size(); i++) { for (j = 0; j < graph.size(); j++) { if (graph[i][k] + graph[k][j] < graph[i][j]){ graph[i][j] = graph[i][k] + graph[k][j]; } } } } } int main() { int V,E,s,d,w; while(true){ cin >> V >> E; if(V==0 and E==0) return 0; graph.clear(); graph.resize(V); for(int i = 0 ; i < V ; ++i) { graph[i].resize(V); } for(int i =0; i< graph.size(); i++){ for(int j =0; j< graph.size(); j++){ graph[i][j]= INF; } } for(int i=0; i<E; i++){ cin >> s >> d >> w; if(graph.at(d-1).at(s-1)==INF){ graph.at(s-1).at(d-1) = w; } else{ graph.at(s-1).at(d-1) = 0; graph.at(d-1).at(s-1) = 0; } } floyd_warshall(); int n; cin >> n; while(n--){ cin >> s >> d; if(graph.at(s-1).at(d-1)<INF and graph.at(d-1).at(s-1)<INF){ cout << 0 << endl; } else{ if(graph.at(s-1).at(d-1)<INF){ cout << graph.at(s-1).at(d-1) << endl; } else{ cout << "Nao e possivel entregar a carta" << endl; } } } cout << endl; } return 0; } |
