# Task 5 – Constrained Shortest Path in a Directed Graph

## Goal

Your goal is to compute a valid path in a small directed, weighted graph from the start node `v1` to the target node `v8`, subject to a set of hard constraints. Among all valid paths, you must pick the one with the minimum total edge weight.

## Graph

The directed, weighted graph for this task is shown in the diagram below. Each edge label is a non-negative integer weight on that directed edge.

## Start, Target, and Valid Paths

- The graph is directed.
- The start node is `v1`.
- The target node is `v8`.
- A path must follow the direction of edges (respect arrow directions).
- A valid path must be simple: no node may appear more than once in the path.

### Additional constraints

- The path must include both `v4` and `v6`.
- `v4` must appear before `v6` along the path.
- The path must never visit node `v3`.
- Among all simple paths from `v1` to `v8` that satisfy the above rules, you must choose the one with the minimum total weight (sum of edge weights along the path).

This instance is designed so that there is exactly one path that satisfies all constraints and has the minimum possible total weight.

## Your Program

Implement your solution in:

    solutions/task5/find_path.py

Your program may hard-code the graph structure after inspecting the diagram. It does not need to read any other input files.

The evaluation harness will run:

    python solutions/task5/find_path.py > results/task5_answer.txt

## Output Format and Location

You must write your final answer to:

    results/answer.txt

The file must contain at least the first line below, and may optionally contain a second line.

- Line 1 (required):
  `PATH: v1->v2->v3->v4->v5->v8`
  Use `->` as the separator, with no spaces. The above example is just an example for reference.
- Line 2 (optional):
  `TOTAL_WEIGHT: <integer>`

The evaluation system will compare the path sequence on the first line byte-for-byte against the reference answer. Any difference in content, spelling, capitalization, or formatting will be marked incorrect.