Data: 14/9 (3a feira ate as 8h da manha)

Pode ser feito individualmente ou em grupos de até 3 pessoas.

Contaminação numa rede de pessoas

Vamos assumir que nos temos uma rede de interação de pessoas representado por um grafo não direcionado com pesos. Cada pessoa é um nó/vertice no grafo e o peso da aresta entre o no A e B é a frequencia ou intensidade de conexão entre A e B (por exemplo assuma que esse peso mede o numero de vezes no mes que A e B conversam).

Se uma membro do grafo é contaminado por um virus, queremos determinar em quanto tempo todos os nós do grafo estarão contaminados. O tempo de contaminação entre A e B é o inverso da frequencia de contato entre A e B (se A e B se falam 4 vezes for mes, o tempo de contaminação entre A e B é 1/4 ou 0.25 de um mes.

Algoritmo

esse problema de encontrar o menor caminho de um vertice para dodos os vertices de um grado é conhecido como shortest-path tree. A solução é uma pequena variação do algoritmo de Dykstra. No Dykstra voce tem a fonte e o destino, e constroi as estruturas de dados do algoritmo partindo da fonte e termina quando fronteira atinge o destino. No caso do shortest path tree voce continua o algoritmo até que todos os vertices tenham sido visitados.

Veja que para esse problema nos não precisamos do caminho do no origem a todos os outros nós. Precisamos apenas do tempo para a contaminação.

Formato dos dados

Os dados do programa serão no seguinte formato:

antonio beto 5.4
antonio denise 1.2
fabio edite  9.3
...
fabio zelia 4.5

antonio

As linhas como antonio beto 5.4 indica que do no antonio para o nó beto a frequencia de contato é 5.4 (vezes por mes). Após todas as linhas to tipo acima, há uma linha em branco, e uma linha com o nome de um nó que é o nó contaminado.

Os dados serão lidos do standard input.

A saida deve ser no formato:

3.14

um número com 2 casas decimais que indica o tempo minimo para que todos sejam contaminados.

Voce pode assumir que o grafo é conectado, ou seja existe um caminho entre quaisquer 2 nós do grafo.

Voce nao precisa usar estruturas de dados complexas como um “priority queue” que sao O(1) para achar o minimo. Pode fazer uma busca linear para achar o mínimo e usar as funções já disponíveis no Haskell.

Voce nao pode usar nenhum pacote do Haskel que nao as bibliotecas padrão. .

Submissão

• submeta via Classroom, ate 3a feira dia 14 ate as 8h da manha,

• submeta um arquivo apenas, com o programa haskell.

• seu programa (cujo nome é digamos projeto.hs) sera executado como

runhaskell projeto.hs < dados.txt 

ou seja o programa deve ler do standard input e imprimir a saida no standard output.

• eu testarei seu programa em alguns arquivos que representam diferentes versões do problema acima.

• programas que nao compilam ou que não rodam não receberão nota.