CacheDB: 2026-06-01 10:30:08

2768-grafo-do-dabriel

grafo-do-dabriel

C Difficulty

README.md Preview

# 2768 - Grafo do Dabriel | **Version**: 0.5
`grafo-do-dabriel` | Difficulty: **C** | **Updated**: 2026-05-16 13:52:05

**Sync Status:** ✅ Local: OK | ❌ Maratona: Not in DB | ❌ API: Not in DB

## Overview
Adaptação engenhosa do Algoritmo de Floyd-Warshall, usando a definição nativa do limite K de vértices intermediários para resolver consultas.

## Metadata
- **Author**: Unknown
- **Editorial**: Em problemas que perguntam o menor caminho do vértice U até o vértice V,
com a restrição explícita de que os "vértices visitados no meio (intermediários)
devem ser menores ou iguais a K", estamos de frente a EXATA DEFINIÇÃO 
do algoritmo de Floyd-Warshall!
Na tripla de laços do FW: k de 1..N, i de 1..N, j de 1..N.
A matriz dp[k][i][j] é exatamente a resposta para "Menor Caminho de i a j 
usando apenas intermediários <= k".
Deste modo, basta guardarmos a matriz inteira em um histórico 3D
`dist[k][i][j]` durante as fases. Assim, as consultas são respondidas em O(1).

- **Success Msg**: Isso é dominar os preceitos de uma fórmula DP: saber como e porquê a iteração k do Floyd-Warshall funciona é um diferencial gigante!

| Time Limit | Memory Limit | Time Complexity | Space Complexity |
| :--- | :--- | :--- | :--- |
| -s | -MB | O(N^3 + Q) | - |

## Stats
| Metric | Count |
| :--- | :--- |
| Test Scenarios | 21 |
| Solutions | 1 |

## Statements
| ID | Status | Level | Natural Languages | Skills |
| :--- | :--- | :--- | :--- | :--- |
| `a-dabriel` | ✅ | A | pt | floyd-warshall, dp-graphs |

## Test Scenarios
| Name | Description | Count | Type | Level | Skills | DB Sync |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| **Carga N³ e Q Alta** | N até 100, Q até 10^5. | 3 | Performance | A | floyd-warshall | - |
| **Casos Diversos e Múltiplos Testes** | Tratar múltiplos arquivos EOF e grafos soltos. | 15 | TDD | B | basic-io | - |
| **K Menor Que Possível** | Responder caminhos inexistentes. | 2 | TDD | C | logic | - |
| **Exemplo** | Base. | 1 | TDD | D | basic-io | - |

## Solutions
- **Floyd-Warshall (3D DP)** (`a-otima-basica`)
  - Languages: `cpp, py, java`

## Components
- ✅ Statements
- ✅ Solutions
- ✅ Test Cases

Actions

Workflow do Problema

Local Workspace

Pasta criada no disco
Metadados

Informações básicas preenchidas
Validação

Soluções passam nos testes
4

Sincronização

Enviado para DB e GitLab

Components

Statements ✅
Solutions 1 ✅
Test Cases 21 ✅

Database Info

DB ID 2768

Name Grafo do Dabriel

Time Limit 1.0s

Mem Limit 256 MB

Version 0.5

Difficulty Level O

Test Cases 0

🚀 Quick Prompts

Structure Scaffolding

Generate metadata & folder structure

ID: 1.1

Context & Description

Draft description & editorial

ID: 1.2

Statements List

⚠️

Warning: The defaultStatement defined in metadata (a-dabriel) was not found in the file system.

ID	Level	Natural Languages	Skills	Status	Action
a-dabriel	A	a c d	floyd-warshall, dp-graphs	⚠️

Statement Details

Select a statement above to view details.

Actions

Statistics

1 Total Statements

By Type (ID)

a-dabriel 1

By Level

Level A 1

🚀 Quick Prompts

Statement Analysis

Analyze ambiguity & clarity

ID: 2.1

WOK Statement Generation

Rewrite in WOK Universe theme

ID: 2.2

Statement Expansion

Expand to 4 difficulty levels

ID: 2.3

Testcase Scenarios Sync

YAML Source vs Database

Slug	Level	Name	Type	Skills	Status	Actions
`a-performance`	A	Carga N³ e Q Alta N até 100, Q até 10^5.	PERFORMANCE	floyd-warshall 1pts	Not in DB	Details
`b-fuzzing`	B	Casos Diversos e Múltiplos Testes Tratar múltiplos arquivos EOF e grafos soltos.	TDD	basic-io 1pts	Not in DB	Details
`c-edge`	C	K Menor Que Possível Responder caminhos inexistentes.	TDD	logic 1pts	Not in DB	Details
`d-sample`	D	Exemplo Base.	TDD	basic-io 1pts	Not in DB	Details

Local Test Cases (Disk)

Scenario: a-performance 3 cases

Name	Files (Input / Output)	Actions
dabriel-01 📄 📷	Input `dabriel-01.in` 1b97f07ab851b88ec9f566ef6c08edc2 Output `dabriel-01.out` f6ffb9701e75326d51b6fce99b6af239	🔍 Details
dabriel-02 📄 📷	Input `dabriel-02.in` 50b63f365a39823fb2c908e06fbfc190 Output `dabriel-02.out` ae0e498b59b56bc5e53a3ec5565a1010	🔍 Details
dabriel-03 📄 📷	Input `dabriel-03.in` 3bc4d5d6c4f38b2c08cf6cab7f0a7e23 Output `dabriel-03.out` 26ba33c2308ed2ca0926ec9104b31194	🔍 Details

Scenario: b-fuzzing 15 cases

Name	Files (Input / Output)	Actions
dabriel-01 📄 📷	Input `dabriel-01.in` c45141bdf9bbecf9c37e379d0b51335f Output `dabriel-01.out` cade6cb6989eb5a2669dc2552dc2e6e4	🔍 Details
dabriel-02 📄 📷	Input `dabriel-02.in` 6e3136f2ed31e90ebc8b15cdae320f4e Output `dabriel-02.out` 9921cabfc5cf88b71ef60828fd7668ad	🔍 Details
dabriel-03 📄 📷	Input `dabriel-03.in` 5b044abc58d430e2ccfaddb5da1cb944 Output `dabriel-03.out` 5ea63284eb9635f403e913e55ea4d1fa	🔍 Details
dabriel-04 📄 📷	Input `dabriel-04.in` 701d4ab1fce6a1ea29de242d8f89d509 Output `dabriel-04.out` daac0eeafefb4ff4e99506d28ea318b4	🔍 Details
dabriel-05 📄 📷	Input `dabriel-05.in` 7ff106d353f7745cee6846dab3f8a5c8 Output `dabriel-05.out` 5c2ed57cb08c00c3d1961ff778f316b3	🔍 Details
dabriel-06 📄 📷	Input `dabriel-06.in` 87eb23fb69312d8ab97fd1ab1485cd04 Output `dabriel-06.out` 53dabe5c80f1e7ee7413f0c0f56a072d	🔍 Details
dabriel-07 📄 📷	Input `dabriel-07.in` 88956d8377ff8c76f945760fbddc404d Output `dabriel-07.out` 2f237512329882f93db13f8c8c113b19	🔍 Details
dabriel-08 📄 📷	Input `dabriel-08.in` e7563ea2424a5ff1cff647eeae9a31ab Output `dabriel-08.out` ca43cc973ffeb7bf49cfa611d9a48251	🔍 Details
dabriel-09 📄 📷	Input `dabriel-09.in` 5bb50bd06237132e318c7a80a7198a21 Output `dabriel-09.out` 4f9ccdc7da608f6a857ed1a96bdfd8c2	🔍 Details
dabriel-10 📄 📷	Input `dabriel-10.in` 777167711dd148f0fa3cad4b48dd2d99 Output `dabriel-10.out` 1e1391972470621778fc56c8cd18e16f	🔍 Details
dabriel-11 📄 📷	Input `dabriel-11.in` 920e325dab84eed53b52964cb4efdb04 Output `dabriel-11.out` 5ac7bccad10887961252494471ddf95f	🔍 Details
dabriel-12 📄 📷	Input `dabriel-12.in` 2f7a1196d92adffa25af0532d94b6edd Output `dabriel-12.out` a5db75fedf5636c90f16734ff700f660	🔍 Details
dabriel-13 📄 📷	Input `dabriel-13.in` 13de77976f68db179ae4be32c84147d8 Output `dabriel-13.out` 4a99e528b6268ec59efd3f40e199e683	🔍 Details
dabriel-14 📄 📷	Input `dabriel-14.in` 3086f70a0c904fce4762f5841564c8e0 Output `dabriel-14.out` 3c215fee8b875d43ec3b33817b127adb	🔍 Details
dabriel-15 📄 📷	Input `dabriel-15.in` 6d161e6602bdde0387dbfcf9ea765bcf Output `dabriel-15.out` ef00b7b3864d234162fd8b5fde680f64	🔍 Details

Scenario: c-edge 2 cases

Name	Files (Input / Output)	Status	Actions
dabriel-01 📄 📷	Input `dabriel-01.in` adb82025925b982c0b1f8b34745fdbb0 Output `dabriel-01.out` 5d684b1c2e8ff0aa9fca8841b07a400e		🔍 Details
dabriel-02 📄 📷	Input `dabriel-02.in` 3e0191802f85f239523f0d99ca784a9f Output `dabriel-02.out` c7c8d45e0fc1a2ac188f9b0a62f1a797		🔍 Details

Scenario: d-sample 1 cases

Name	Files (Input / Output)	Status	Actions
dabriel-01 📄 📷	Input `dabriel-01.in` 8a9524f4bc80eb4f70e52bb4a7b17746 Output `dabriel-01.out` 5864154ff73ce14d0b91000a66fd450f		🔍 Details

📊 Sync Statistics

Total (Disk) 21

Total (Database) 0

✓ Synchronized 0

⚠ Desynchronized 21

Duplicates (MD5)

Duplicates in (MD5) 0

Desync = (DB missing on Disk) + (Disk missing on DB)

Actions

Floyd-Warshall (3D DP)

ID: a-otima-basica

Guarda todos os níveis do K numa Matriz 3D.

Implementations

Solutions Check Report

## Solutions Check Report (Detalhado / Debug)
**Generated**: 2026-06-01T14:03:20.268607
**Solution**: `solutions/a-otima-basica/dabriel.py`

### Compilation
✅ No compilation needed

### Resultados

<table class="results-table"><thead><tr><th>Test Case</th><th>Result</th><th>Time (s)</th></tr></thead><tbody>
<tr class="scenario-row"><td colspan="3"><strong>a-performance - Performance</strong></td></tr>
<tr id="row-a-performance-dabriel-01-in"><td>dabriel-01.in</td><td>✅ PASS</td><td>0.290</td></tr>
<tr id="row-a-performance-dabriel-02-in"><td>dabriel-02.in</td><td>✅ PASS</td><td>0.286</td></tr>
<tr id="row-a-performance-dabriel-03-in"><td>dabriel-03.in</td><td>✅ PASS</td><td>0.286</td></tr>
<tr class="scenario-row"><td colspan="3"><strong>b-fuzzing - TDD</strong></td></tr>
<tr id="row-b-fuzzing-dabriel-01-in"><td>dabriel-01.in</td><td>✅ PASS</td><td>0.015</td></tr>
<tr id="row-b-fuzzing-dabriel-02-in"><td>dabriel-02.in</td><td>✅ PASS</td><td>0.014</td></tr>
<tr id="row-b-fuzzing-dabriel-03-in"><td>dabriel-03.in</td><td>✅ PASS</td><td>0.014</td></tr>
<tr id="row-b-fuzzing-dabriel-04-in"><td>dabriel-04.in</td><td>✅ PASS</td><td>0.034</td></tr>
<tr id="row-b-fuzzing-dabriel-05-in"><td>dabriel-05.in</td><td>✅ PASS</td><td>0.035</td></tr>
<tr id="row-b-fuzzing-dabriel-06-in"><td>dabriel-06.in</td><td>✅ PASS</td><td>0.022</td></tr>
<tr id="row-b-fuzzing-dabriel-07-in"><td>dabriel-07.in</td><td>✅ PASS</td><td>0.033</td></tr>
<tr id="row-b-fuzzing-dabriel-08-in"><td>dabriel-08.in</td><td>✅ PASS</td><td>0.031</td></tr>
<tr id="row-b-fuzzing-dabriel-09-in"><td>dabriel-09.in</td><td>✅ PASS</td><td>0.020</td></tr>
<tr id="row-b-fuzzing-dabriel-10-in"><td>dabriel-10.in</td><td>✅ PASS</td><td>0.030</td></tr>
<tr id="row-b-fuzzing-dabriel-11-in"><td>dabriel-11.in</td><td>✅ PASS</td><td>0.013</td></tr>
<tr id="row-b-fuzzing-dabriel-12-in"><td>dabriel-12.in</td><td>✅ PASS</td><td>0.021</td></tr>
<tr id="row-b-fuzzing-dabriel-13-in"><td>dabriel-13.in</td><td>✅ PASS</td><td>0.024</td></tr>
<tr id="row-b-fuzzing-dabriel-14-in"><td>dabriel-14.in</td><td>✅ PASS</td><td>0.022</td></tr>
<tr id="row-b-fuzzing-dabriel-15-in"><td>dabriel-15.in</td><td>✅ PASS</td><td>0.026</td></tr>
<tr class="scenario-row"><td colspan="3"><strong>c-edge - TDD</strong></td></tr>
<tr id="row-c-edge-dabriel-01-in"><td>dabriel-01.in</td><td>✅ PASS</td><td>0.013</td></tr>
<tr id="row-c-edge-dabriel-02-in"><td>dabriel-02.in</td><td>✅ PASS</td><td>0.013</td></tr>
<tr class="scenario-row"><td colspan="3"><strong>d-sample - TDD</strong></td></tr>
<tr id="row-d-sample-dabriel-01-in"><td>dabriel-01.in</td><td>✅ PASS</td><td>0.014</td></tr>
</tbody></table>

✅ Verification

Validate your solutions against test cases using the metadata rules.

🚀 Quick Prompts

Solution Generation

Create Optimal/Sub-optimal code

ID: 3.1

📄 Enunciados

A 1

Idiomas: pt

💡 Soluções

cpp: 1 py: 1 java: 1

✅ 0 ❌ 0

🧪 Casos de Teste

4 Scen.

Total no Disco 21

Total no Banco 0

Sincronização 0.0%

Metadata (form)

Version

Name

Slug

ID Beecrowd

Difficulty

Time Complexity

Space Complexity

Time Limit (s)

Memory Limit (MB)

Origin

Author (Problem)

Author (Editorial)

Default Statement

Topics

Skills

Description

Editorial

Success message

metadata.yaml

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 2768 name: "Grafo do Dabriel" slug: "grafo-do-dabriel" timelimit: 1.0 memlimit: 200 difficultyLevelId: C author: "Gabriel Duarte" origin: "Beecrowd" description: 'Adaptação engenhosa do Algoritmo de Floyd-Warshall, usando a definição nativa do limite K de vértices intermediários para resolver consultas.' editorial: | Em problemas que perguntam o menor caminho do vértice U até o vértice V, com a restrição explícita de que os "vértices visitados no meio (intermediários) devem ser menores ou iguais a K", estamos de frente a EXATA DEFINIÇÃO do algoritmo de Floyd-Warshall! Na tripla de laços do FW: k de 1..N, i de 1..N, j de 1..N. A matriz dp[k][i][j] é exatamente a resposta para "Menor Caminho de i a j usando apenas intermediários <= k". Deste modo, basta guardarmos a matriz inteira em um histórico 3D `dist[k][i][j]` durante as fases. Assim, as consultas são respondidas em O(1). successmsg: 'Isso é dominar os preceitos de uma fórmula DP: saber como e porquê a iteração k do Floyd-Warshall funciona é um diferencial gigante!' timeComplexity: O(N^3 + Q) skills: - floyd-warshall - dp-graphs statements: - id: a-dabriel testScenarioLevel: A thematicSkills: - skill: floyd-warshall points: 2 - skill: dp-graphs points: 1 testScenarios: - id: a-performance name: Carga N³ e Q Alta description: "N até 100, Q até 10^5." helpTip: "Rodar Dijkstra por consulta daria TLE. Você deve pré-processar Floyd-Warshall." level: A testType: PERFORMANCE skills: - skill: floyd-warshall points: 1 - id: b-fuzzing name: Casos Diversos e Múltiplos Testes description: "Tratar múltiplos arquivos EOF e grafos soltos." helpTip: "Você resetou a matriz 3D para o valor infinito no início de cada caso?" level: B testType: TDD skills: - skill: basic-io points: 1 - id: c-edge name: K Menor Que Possível description: "Responder caminhos inexistentes." helpTip: "A saída deve ser -1 para impossíveis." level: C testType: TDD skills: - skill: logic points: 1 - id: d-sample name: Exemplo description: "Base." helpTip: "Exemplo bate." level: D testType: TDD skills: - skill: basic-io points: 1 solutions: - id: a-otima-basica name: Floyd-Warshall (3D DP) description: Guarda todos os níveis do K numa Matriz 3D. level: A implementations: - language: cpp paradigm: Imperative main: dabriel.cpp filenames: - dabriel.cpp - language: py paradigm: Imperative main: dabriel.py filenames: - dabriel.py - language: java paradigm: OO main: Dabriel filenames: - Dabriel.java authorSlugProblem: Unknown defaultStatement: a-dabriel

2768-grafo-do-dabriel

README.md Preview

Actions

Workflow do Problema

Local Workspace

Metadados

Validação

Sincronização

Components

Database Info

🚀 Quick Prompts

Statements List

Statement Details

Actions

Statistics

By Type (ID)

By Level

🚀 Quick Prompts

📊 Sync Statistics

Actions

Test Case Details

Testcase Scenarios Sync

Local Test Cases (Disk)

Scenario: a-performance 3 cases

Scenario: b-fuzzing 15 cases

Scenario: c-edge 2 cases

Scenario: d-sample 1 cases

📊 Sync Statistics

Actions

Floyd-Warshall (3D DP)

Implementations

Solutions Check Report

✅ Verification

🚀 Quick Prompts

📄 Enunciados

💡 Soluções

🧪 Casos de Teste

Metadata (form)

Git Status

Git Workflow

Problem Analysis Report

🛠️ Validation Tools

✅ Synced with API

✅ Synced with Database

Actions

📋 Processo de Criação

Select a Prompt

📤 API Synchronization

📄 Recreating README.md...

💻 Git Action Output

Running Verification...

Ajuda

📄 Sync Statements to DB

🚀 Batch Auto-Link Process

⬇️ Repo Sync Output

📝 Update Manifest Output

Ajuda