0336-virus-h1n1

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.4" id: 336 name: Vírus H1N1 slug: virus-h1n1 timeLimitSegs: 1.0 difficultyLevelId: F author: Unknown origin: UNITRI 2016 description: | Encontre a duração do caminho temporal mais rápido entre dois nós a e b. Um grafo temporal possui arestas representadas por (u, v, t), indicando um contato no instante t. Cada nó possui um tempo de retenção R antes de poder repassar o vírus. editorial: | **Briefing para o Professor:** Este problema é uma excelente introdução a grafos com pesos dependentes do tempo (Time-Expanded ou grafos temporais). O número baixíssimo de arestas (A <= 20) permite que o problema seja resolvido com uma Busca em Profundidade (DFS) de força-bruta para enumerar todos os caminhos possíveis do nó `a` ao nó `b` sem causar TLE (Time Limit Exceeded). **Estratégia de Resolução:** Construa um DFS cujo estado guarde `(nó_atual, t_ultimo_contato, t_primeiro_contato)`. Ao iniciar a partir de `a`, para cada aresta adjacente `(a, vizinho, t)`, passe `t` tanto para o último contato quanto para o primeiro. A regra de transição é simples: uma aresta `(u, v, t)` só é válida se `t >= t_ultimo_contato + R`. Se o nó atual for `b`, calcule a duração com `t_ultimo_contato - t_primeiro_contato` e atualize a menor duração global. Importante: "Se não existir caminho ou o caminho for composto por apenas uma aresta, a duração é zero." successmsg: 'Isolamento bem-sucedido! Seu algoritmo rastreou as origens temporais perfeitamente.' timeComplexity: O(A!) skills: - graphs - dfs - recursion statements: - id: a-virus-h1n1 testScenarioLevel: A thematicSkills: - skill: history points: 1 testScenarios: - id: a-performance name: Busca Massiva (Grafo Denso Relativo) description: "Caminhos múltiplos até A=20 simulando todas as permutações temporais." helpTip: "Cuidado, se houver muitos caminhos e você esquecer da restrição de R, pode dar loop infinito (ou não, pois R >= 1)." level: A testType: PERFORMANCE skills: - skill: recursion points: 1 - id: b-edge-cases name: Casos sem Caminho ou 1 Aresta description: "Casos listados no enunciado em que o vírus não tem tempo de retenção ou tem caminho de tamanho 1." helpTip: "Você retornou zero se o caminho for composto por 1 aresta (ou se for inalcançável)?" level: B testType: TDD skills: - skill: dfs points: 1 - id: c-basic name: Grafo em Linha description: "Caminho único linear com e sem a restrição temporal ativada." helpTip: "Seu algoritmo acumulou os tempos ou apenas tentou passar os limites da restrição R?" level: C testType: TDD skills: - skill: graphs points: 1 - id: d-sample name: Exemplos do Enunciado description: "Exemplos idênticos aos do PDF." helpTip: "Para as arestas em string, usou formatação ou regex para quebrar nas vírgulas?" level: D testType: TDD skills: - skill: graphs points: 1 solutions: [] authorSlugProblem: Unknown defaultStatement: a-virus-h1n1