URI PROBLEMA 1227 - Perdido na Noite SOLUÇÃO EM C++

URI Online Judge | 1227

Perdido na Noite

Maratona de Programação da SBC  Brasil

Timelimit: 2

Numa cidade da Nlogônia, o sistema viário é composto de N rotatórias e N−1 ruas, sendo que cada rua liga duas rotatórias distintas. Utilizando o sistema viário, é possível ir de qualquer rotatória para qualquer outra rotatória da cidade.

A cidade possui apenas dois hotéis: um barato, localizado na rotatória B, e um caro, localizado na rotatória C. Um turista veio à cidade para celebrar o aniversário de um amigo, cuja festa está sendo realizada em um clube localizado na rotatória A. Como o turista não fez reserva em nenhum dos hotéis e a noite está agradável, após a festa ele decidiu passear a pé pelas ruas e rotatórias até encontrar um dos hotéis (ele também decidiu hospedar-se no primeiro hotel que encontrar).

Seu plano foi dificultado porque como ele não conhece a cidade e bebeu um pouco além da conta, todas as ruas lhe parecem iguais. Assim, ele decidiu usar a seguinte estratégia: a cada rotatória ele escolhe, com probabilidade uniforme, uma das ruas que saem da rotatória, e usa essa rua para ir a uma outra rotatória, até chegar à rotatória onde um dos hotéis está localizado. Note que como o turista não consegue distinguir as ruas, pode ocorrer de ele escolher a mesma rua pela qual chegou à rotatória.

Você deve escrever um programa que, dadas a descrição do sistema viário, a localização A da festa de aniversário, a localização B do hotel barato e a localização C do hotel caro, determine a probabilidade de o turista chegar ao hotel barato antes de chegar ao hotel caro.

Entrada

A primeira linha de um caso de teste contém quatro inteiros N (3 ≤ N ≤ 100), A (1 ≤ A), B e C (C ≤ N), indicando respectivamente o número de rotatórias do sistema viário, a rotatória onde a festa de aniversário foi realizada, a rotatória onde o hotel barato está localizado, e a rotatória onde o hotel caro está localizado. Cada uma das N−1 linhas seguintes contém dois inteiros X (1 ≤ X) e Y (Y ≤ N), indicando que existe uma rua que liga as rotatórias X e Y.

Nota: B != C, A != B, A != C e X != Y

Saída

Seu programa deve imprimir uma única linha, contendo a probabilidade de o turista chegar ao hotel barato antes de chegar ao hotel caro, com 6 casas decimais.

#include <cstdio>

#include <vector>

#define MAXN 101

using namespace std;

vector<int> grafo[MAXN];

int processado[MAXN],pai[MAXN],nivel[MAXN],N,A,B,C;

void dfs(int x){

processado[x] = 1;

for(int i=0;i<grafo[x].size();i++){

int v = grafo[x][i];

if(!processado[v]){

pai[v] = x;

nivel[v] = nivel[x] + 1;

dfs(v);

}

}

}

int LCA(int u, int v){

while(u != v){

if(nivel[u] > nivel[v]){

u = pai[u];

}

else{

v = pai[v];

}

}

return u;

}

int main(){

while(scanf("%d %d %d %d",&N,&A,&B,&C) != EOF){

for(int i=1;i<=N;i++){

grafo[i].clear();

pai[i] = -1;

processado[i] = 0;

nivel[i] = -1;

}

for(int i=1;i<N;i++){

int u,v;

scanf("%d %d",&u,&v);

grafo[u].push_back(v);

grafo[v].push_back(u);

}

nivel[A] = 0;

pai[A] = 0;

dfs(A);

int ancestral = LCA(B,C);

int distb = nivel[B] - nivel[ancestral];

int distc = nivel[C] - nivel[ancestral];

double prob = double(distc)/double(distb + distc);

printf("%.6lf\n",prob);

}

return 0;

}