Olá meus amigos nerds. Hoje vamos ajudar o povo da Costa do Mosquito a instalar um posto de vacinação. Já que é isso que o problema 1332. Dengue nos pede para fazer. Mais especificamente, dado um conjunto de cidades e as rotas que as ligam, determinar em qual cidade deve ser instalado o posto de vacinação de modo a minimizar a distância percorrida por quem mora mais longe do posto.
Solução
Esse problema implora que usemos grafos para modela-lo. As cidades são os vértices e as rodovias as arestas. Como a entrada do problema é bem pequena, basta então calcular a distância entre todas as cidades e escolher a cidade que tem a menor distância máxima. Para calcular a distância de uma cidade para todas as outras podemos usar o algoritmo de dijkstra. Facinho né!
Nenhum comentário:
Postar um comentário