reports_under8000/TRAINING_REPORT.md

Training Report: CodeX Qwen2.5 0.5B Under-8000 Unsloth LoRA

Deliverable

This repo contains the Option A LoRA deliverable: the public base model plus the trained LoRA adapter. It is not a merged full-weight model, but it can be reused directly for inference and can be merged later.

Run summary

• Run: under8000 post-inference
• Base model: unsloth/Qwen2.5-0.5B-Instruct
• Source dataset: Modotte/CodeX-2M-Thinking, first 1,000,000 rows formatted as Qwen ChatML
• Filter: strict formatted token length < 8000 using Qwen tokenizer
• Max sequence length: 8192
• Final observed train loss: 0.7097312450408936
• Final observed eval loss: 0.7063287496566772
• Final observed step: 74653
• Finished: 2026-05-12T03:08:43.448180+00:00

How to use later

from unsloth import FastLanguageModel
model, tokenizer = FastLanguageModel.from_pretrained(model_name='unsloth/Qwen2.5-0.5B-Instruct', max_seq_length=8192, load_in_4bit=True)
# Load the adapter from this HF repo final_lora_adapter_under8000 folder, or from a local downloaded copy.
# For PEFT/Transformers workflows, use PeftModel.from_pretrained(base_model, adapter_path).
FastLanguageModel.for_inference(model)

Inference samples

Sample 1

Prompt: Implement a Python function longest_substring_without_repeating(s) that returns the length of the longest substring without repeated characters. Explain the sliding-window idea briefly.

Output:

<think>
Okay, I need to implement the longest substring without repeating characters using the sliding window technique. Let me think about how this works.

First, what's a substring? Oh right, it's any contiguous sequence of characters within the string. So for example, in "abcabcbb", the longest is "abc" or "bca" or "cab", etc., but wait no, actually the answer here would be 3 because after 'a', there's another 'a' later, so you can't have 'ab' anymore. Wait, maybe I should check examples.

Wait, let's take "abba". The longest substring without repeats is "ab" (length 2), then when we get to 'b' again, we can't include it. Then the next 'a' comes, which is already in the current window. So the maximum is 2 as well.

So the approach is to maintain a window [left, right] where all characters are unique. As we iterate through each character with the right pointer, if it's already in the current window, we move left forward until the duplicate is removed. But since we want the longest possible window, we need to keep track of the maximum length found during this process.

Let me outline the steps:

Initialize left = 0, max_length = 0, and a dictionary to keep track of the last index of each character.

Loop over each right from 0 to len(s)-1:
    If s[right] is in the dictionary and its last occurrence is >= left, then update left to be the position after the previous occurrence.
    Update the dictionary with the current character's index.
    Calculate the current window size (right - left + 1). Compare with max_length and update if necessary.

Yes, that makes sense. Because by moving the left pointer whenever a duplicate is found, we ensure that the current window has all unique characters. And since we're looking for the longest such window, once we find a longer one, we keep updating the max_length.

Now, implementing this in Python. Let's see.

The function will take s as input. We'll initialize variables: left=0, max_len=0, char_map={}, duplicates = {}.

Then loop through each right in range(len(s)):

Check if s[right] is in char_map and char_map[s[right]] >= left. If yes, set left to char_map[s[right]] + 1.

Update char_map[s[right]] to right.

Compute current window length (right - left + 1). If it's larger than max_len, update max_len.

At the end, return max_len.

But wait, what about cases where the same character appears multiple times? For example, "aaaaa"? The first time, left moves to 0, then the second a is added, left becomes 1. Then third a is checked, which is in char_map at 1, but left is now 1, so left becomes 2. Then fourth a is in char_map at 2, left becomes 3. Then fifth a is in char_map at 3, left becomes 4. So the window is 4-4+1=1, which is correct.

Another test case: "abba".

Right starts at 0 (char 'a'), not in map. Add to map. Current window is 0-0, length 1. Max is 1.

Right 1 (char 'b'): not in map. Add. Window 0-1, length 2. Max is 2.

Right 2 (char 'b'): exists in map at 1. Since left is 0, which is <=1, so left becomes 2. Update map['b'] to 2. Current window is 2-2, length 1. Max remains 2.

Right 3 (char 'a'): exists in map at 0. Since left is 2, which is >0, so left becomes 0+1=1. Update map['a'] to 3. Current window is 1-3, length 3. Max becomes 3.

So the result is 3, which is correct.

So this logic seems solid.

Now, code-wise, in Python:

def longest_substring_without_repeating(s):
    char_map = {}
    left = 0
    max_len = 0
    for right in range(len(s)):
        current_char = s[right]
        # Check if current_char is in the map and its last occurrence is >= left
        if current_char in char_map and char_map[current_char] >= left:
            left = char_map[current_char] + 1
        # Update the map with the current index
        char_map[current_char] = right
        # Update the max length
        current_length = right - left + 1
        if current_length > max_len:
            max_len = current_length
    return max_len

Testing this function with some examples.

Test case 1: "abcabcbb"

Expected output: 3 (abc)

Let's walk through:

For each step:

right=0 (a): not in map. add. current_length 1. max 1.

right=1 (b): add. current_length 2. max 2.

right=2 (c): add. current_length 3. max 3.

right=3 (a): exists in map at 0. left becomes 1. update a's index to 3. current_length 3 (3-1+1=3). max still 3.

right=4 (b): exists in map at 1. left is 1. So left becomes 2. update b's index to 4. current_length 4-2+1=3

Sample 2

Prompt: Write a Python function to merge overlapping intervals. Input is a list of [start, end] pairs; return sorted non-overlapping intervals.

Output:

<think>
Okay, I need to write a Python function that merges overlapping intervals from a given list of start and end times into non-overlapping ones. Let's think about how to approach this.

First, the input is a list of intervals. Each interval has two elements: start and end. The output should be a list of non-overlapping intervals sorted in order. So, for example, if the input is [[1,3], [2,4], [5,7]], the merged result would be [[1,4], [5,7]] because 3 overlaps with 2-4, then 5-7 starts after 4 ends.

Hmm, how do I find overlapping intervals? Well, one common method is to sort the intervals based on their start times. Then, iterate through them, checking if the current interval overlaps with the previous one. If it does, we keep the previous one; otherwise, we add the new one.

Wait, but what if there are multiple overlapping intervals? Like, suppose after sorting, some intervals overlap with each other. But since we process them in order, once an interval is added, any subsequent intervals that start before or at the same time as the previous might also overlap. Wait no, because when you sort by start time, all the intervals are ordered. So if the next interval starts before the previous ends, they can't overlap. Only if the next interval starts exactly when the previous ends, they do overlap.

So the steps could be:

1. Sort the intervals based on their start values.
2. Initialize a result list with the first interval.
3. Iterate over the sorted intervals starting from the second one:
   a. For each interval, compare its start with the end of the last interval in the result.
   b. If the start of the current interval is less than or equal to the end of the last interval in the result, then this interval doesn't overlap with the last one. Add it to the result.
   c. Otherwise, add the current interval to the result.

But wait, what if the current interval's start is greater than the end of the last interval? That means it starts after the last ended. So it must overlap with the last interval. Because if the start is after the end, then the interval starts after the previous ended. So adding it would create an overlap.

Yes, so the condition is: if the current interval's start <= last_end, then it overlaps. Otherwise, it doesn't.

So let's outline the algorithm:

Sort the intervals by start time.

Initialize last_start = None, result = []

For each interval in sorted list:
    if last_start is not None and interval.start <= last_start:
        # Overlap, add to result
        result.append(interval)
    else:
        # No overlap, add to result
        result.append(interval)

This way, we only add intervals that don't overlap with the last one in the result.

Let me test this logic with some examples.

Example 1: [[1,3], [2,4], [5,7]]

After sorting: [[1,3], [2,4], [5,7]]

Process first interval (1,3). Since last_start is None, add to result. Now result is [[1,3]].

Next interval [2,4]. Check if 2 <= 3 (last_start is 1). Yes. So add to result. Result becomes [[1,3], [2,4]].

Next interval [5,7]. Check 5 <=4? No. So add to result. Final result is [[1,4], [5,7]]. Correct.

Another example: [[1,4], [2,3], [6,8]]

Sorted: [[1,4], [2,3], [6,8]]

First interval [1,4]. Add to result.

Second interval [2,3]. Start is 2 <=4. So add. Result now [[1,4], [2,3]].

Third interval [6,8]. Start is 6 >3. So add. Result becomes [[1,4], [2,3], [6,8]]. Which is correct.

Another case where intervals are completely contained within others. Like [[0,1], [2,3], [4,5]]. Sorted. First interval adds. Second starts at 2 which is <=1? No. Third starts at4>1. So adds. So merged is [[0,1], [2,3], [4,5]].

What about overlapping intervals that are adjacent? Like [[1,2], [2,3]]. Sorted. First interval adds. Second starts at 2 <=2. So adds. Merged is [[1,2], [2,3]].

Edge cases: empty list? Probably returns empty. Single interval returns itself.

Now, implement this in Python.

The function will take a list called intervals. We need to sort it. So:

def merge_overlapping_intervals(intervals):
    # Sort the intervals based on start time
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    result = []
    last_start = None
    for interval in sorted_intervals:
        start, end = interval
        if last_start is not None and start <= last_start:
            result.append(interval)
        else:
            result.append(interval)
    return result

Wait, but what if the input is empty? Then sorted_intervals is empty, loop doesn't run, returns empty list. Which is correct.

Testing another case: [[5,9], [1,3], [7,10]]. Sorted as is. Process:

First interval [5,9]. Add. Last_start=5.

Next [1,3]: start 1 <=5. Add. Result

Sample 3

Prompt: Given num_courses and prerequisites pairs [a,b], implement can_finish using topological sorting and explain the complexity.

Output:

<think>
Okay, so I need to figure out how to determine if it's possible to finish all courses given their prerequisites. The problem is asking for both the logic of checking if such a completion is possible and explaining the complexity. Let me start by recalling what topological sort does.

Topological sort involves arranging nodes in an order where for every directed edge from node u to v, u comes before v. This ensures that we process all prerequisites before completing the course. So, the idea is to check if there's a cycle in the graph formed by the prerequisites. If there's a cycle, then it's impossible to complete all courses; otherwise, it's possible.

But wait, the user mentioned "complexity" here. How do they explain this? Maybe because the algorithm might have O(n^2) time complexity due to Kahn's algorithm (which uses BFS), but maybe the actual complexity depends on the number of nodes and edges. Alternatively, perhaps the explanation should mention that the algorithm has a time complexity of O(V + E), which is linear in the number of nodes and edges. But the question specifically asks about complexity, not just the time complexity. Hmm.

Wait, the user probably wants us to explain the complexity in terms of the steps involved in the solution. For example, if the algorithm uses DFS or BFS, each step could be considered as a separate operation. But maybe the key is understanding the structure of the graph and how the algorithm checks for cycles.

Let me think: the prerequisite pair [a, b] means that course a must be taken before course b. So, the direction of the edge is from b to a. Wait, no. Wait, if you have a pair like [a, b], meaning a requires b. So, the edge would be from b to a. Because to take b, you need to have taken a first. So the adjacency list for the graph would have edges pointing from the second element to the first. Or maybe the other way around. Let me clarify.

Suppose the prerequisites are [a, b]. Then, the pair [a, b] represents that a depends on b. So, the edge should be from b to a. Because to take b, you must have taken a. So the adjacency list for the graph would have edges from the second element to the first. So, for example, if a has a prerequisite b, then the edge is from b to a. Otherwise, if the pair is [b, a], then the edge is from a to b.

So, when building the adjacency list, each prerequisite pair [a, b] adds an edge from b to a. That makes sense.

Now, the topological sort algorithm works by processing nodes in reverse order. So, if during the traversal, we encounter a node that hasn't been processed yet, we add it to the queue. Each time we process a node, we decrease its in-degree by 1. If any node still has in-degree greater than zero after processing, there's a cycle.

So, the steps are:

1. Build the adjacency list and in-degree count.
2. Initialize a queue with all nodes that haven't been visited yet.
3. While the queue is not empty:
   a. Dequeue a node.
   b. For each neighbor (prerequisites), decrement their in-degree by 1.
   c. If a neighbor's in-degree becomes 0, enqueue it.
4. If the total number of processed nodes equals the number of courses, return True. Else, False.

The complexity here is O(V + E), since each node and edge is processed once. However, the exact implementation might vary based on the approach used. But according to standard algorithms, the time complexity is O(V + E). But the user asked for complexity, not just the time. So maybe the answer should explain why Kahn's algorithm is efficient in terms of time and space?

Alternatively, maybe the explanation should mention that Kahn's algorithm processes nodes level by level, which is O(V + E) time. But the exact implementation might differ. For example, in some implementations, you use a stack instead of a queue, which is more efficient in practice. But the user didn't specify whether to use a queue or a stack. Since the problem mentions "complexity", perhaps the answer should state that the algorithm has a time complexity of O(V + E), which is linear in the number of nodes and edges. But the exact implementation might vary. However, given that the user is asking for the complexity, perhaps the answer should explain that the algorithm has a time complexity of O(V + E), which is linear in the number of nodes and edges. But the exact implementation isn't specified. However, the user might expect a detailed explanation.

Wait, the original problem says "complexity". So maybe the answer should explain that the algorithm has a time complexity of O(V + E), which is linear in the number of nodes and edges. But the exact implementation might vary. However, given that the user is asking for the complexity, perhaps the answer should present the algorithm's time complexity and explain the steps needed to implement it correctly.

Alternatively, maybe the complexity refers to the number of operations required to perform the algorithm. For example, in some cases, you might have to visit multiple nodes at different levels, leading to O(V + E) operations. But the exact implementation might vary.

In any case, the user wants to know the complexity. So perhaps the answer should explain that the algorithm has a time complexity of O(V + E), which is linear in the number of nodes and edges. But the exact implementation might vary. However, given that the user is asking for the complexity, perhaps the answer should provide a general explanation.

Alternatively, maybe the complexity is the number of operations performed, which is O(V + E). But the exact implementation may

Sample 4

Prompt: Implement an LRU cache in Python with O(1) get and put operations. Use only standard library data structures.

Output:

<think>
Okay, I need to implement an LRU cache using the standard library's data structures. Let me think about how to approach this.

First, what's an LRU cache? It stores items that have been used but not yet removed from memory. So when you add an item, it needs to be added to the front of the list so it can be retrieved later. When removing an item, we need to remove it from the front or back if it was at the end of the list.

The user mentioned using only standard libraries. Oh right, maybe they want us to use deque for efficient insertions and deletions. But wait, the problem says "O(1)" get and put operations. Deques are good for O(1) access, but inserting and deleting from both ends would require O(n) time each, which isn't acceptable here. Hmm, maybe there's another way?

Alternatively, maybe using a linked list structure where each node has a pointer to its previous and next nodes. That way, adding is O(1), removing is also O(1). But implementing a linked list might be more complex than just appending to the front. Maybe the user wants a simple implementation without extra libraries.

Wait, the question says "use only standard library data structures". So perhaps the intended solution uses a list and some other data structures. Like, maybe using a list and keeping track of the last accessed elements. But that's less efficient because each insertion and deletion could take O(n) time. Alternatively, using a dictionary to map keys to their values, then maintaining the order by checking the first element. But dictionaries don't support ordered insertion, so that's not possible.

Hmm. The user probably expects a straightforward implementation using a list and basic operations like append and pop. Because otherwise, the LRU cache would be too slow for large datasets.

So let's outline the steps:

1. Create a list (like a deque) to store the items.
2. Maintain a current index to keep track of the position in the list.
3. For each new item:
   a. Add it to the list at the current index.
   b. Increment the current index.
4. For removal:
   a. Remove the item at the current index.
   b. Decrement the current index by 1.
5. For insertion:
   a. If the list is empty, create a new entry with value equal to the new item.
   b. Otherwise, find the position of the item, move it to the front, and update the current index.

But wait, when moving an item to the front, do we need to check if the item exists in the list? Or does the list handle duplicates automatically? Well, the problem doesn't specify handling duplicates, so maybe just assume that all items are unique. But even if duplicates exist, the list will have them stored as separate entries, so when moving, we need to make sure the existing entry is moved to the front.

Let me test this logic with an example. Suppose the list is [A, B], current index is 0. We add C. Now the list is [C, A, B]. Current index becomes 1. Then we remove A. Since the list is not empty, we look for the item at index 0. It's present, so we move it to the front: [B, A, C]. Current index becomes 0. Then add D. List becomes [D, B, A, C]. Current index increments to 1. Remove B. Move it to front: [A, D, B, C]. Current index 0. And so on.

Yes, that works. So the key points are:

- Using a list for O(1) appends and pops from the front.
- Keeping track of the current index to manage the list's size.
- Handling duplicates by moving the item to the front when necessary.

Now, implementing this in Python. Let's start writing code.

First, import deque from collections. Wait, but the user didn't mention any imports. So assuming that's okay.

Initialize variables:

current_index = 0

cache = []

Then, while True:

Add the next item to the list. Append to cache.

current_index += 1

Check if the list is empty. If yes, create a new entry with value equal to the new item.

Else, find the index of the item at current_index. If found, move it to the front. Else, return None or raise an error.

If the item wasn't found, return None.

For example, suppose the list is [A, B, C], current index is 0. Add D. Cache now [D, A, B, C]. current index 1. Check if D is present. Yes. Move to front: [B, D, A, C]. current index 0. Next item E. Cache becomes [E, B, D, A, C]. current index 1. Check E. Not present. Return None.

This seems manageable.

Testing edge cases: empty list, multiple inserts/removals, duplicates.

Another thing: the problem says "LRU cache", which is exactly what this implementation provides.

So putting it all together.

Wait, but the user said "Use only standard library data structures." So maybe the code should use deque, but perhaps the user wants a simpler implementation. However, given the problem statement, maybe the answer should include the code.

But the user may expect a complete explanation or code submission. Let me check again.

The original question says: Implement an LRU cache in Python with O(1) get and put operations. Use only standard library data structures.

So the code must use only standard libraries. So the code can't use any external modules beyond those listed. So the code must rely solely on

Sample 5

Prompt: Write a function that validates whether a binary tree is a valid BST. Include edge cases and complexity.

Output:

<think>
Okay, I need to write a function to validate if a binary tree is a valid Binary Search Tree (BST). Hmm, let's think about the properties of a BST. 

First, a BST has the property that for every node, all left descendants have values less than the node's value, and all right descendants have values greater than the node's value. Also, there should be no nodes with equal values as children. So, when we traverse down a parent, we can't go back up.

Wait, but how do I check this recursively? Maybe using a helper function that checks each subtree. Let me outline the steps:

1. The root must be a valid BST node.
2. For any node, its left child must be less than the node's value, and the right child must be greater.
3. If a node has both left and right children, they must follow the same rules as the current node.

But wait, what about duplicate values in the left or right subtrees? Like, suppose a left subtree has a 5, which is larger than the current node's value, but then a right subtree also has a 5. That would violate the BST property. So during traversal, whenever we encounter a duplicate value in either the left or right subtree, it's invalid.

So the algorithm could be something like:

- Start at the root.
- Check if the root is null. If yes, return true.
- Recursively check left and right subtrees.
- For each subtree:
   - If left exists and its value is <= root.val: invalid.
   - If right exists and its value >= root.val: invalid.
   - Otherwise, proceed to check the left and right subtrees.

But wait, maybe even after checking the left and right, there might still be duplicates in the left or right. So perhaps during the recursion, we need to track visited values so that we don't process them again.

Alternatively, during the traversal, once a duplicate is found in one side, we can mark that value as invalid immediately. But how?

Let me think of an example. Suppose the root is 4, left is 2, right is 6. Then 2's left is 3, right is 5. Wait, but 3 < 2? No, 3 is smaller. Wait, no. Wait, 2's left is 3, which is less than 2. So that's okay. Then 2's right is 5, which is greater than 2. So that's okay. Then 4's left is 2, which is less than 4. Right is 6, which is greater. So that's valid.

Another example: root is 5, left is 3, right is 7. Then 3's left is 4, which is less than 3. So that's invalid because 3 > 4. So the left child of 3 is invalid. So the entire tree is invalid.

So the approach is to check each node's value against the previous ones. So during the traversal, whenever we visit a node, we compare its value with the existing values in the subtree rooted at that node. If any of those values are equal, return false.

But how to implement this efficiently without storing all previous values? Because for large trees, storing all previous values would take O(n) space, which isn't efficient. So we need a way to track the allowed values as we traverse.

Hmm, maybe a recursive approach where we pass along the allowed range. For example, when we go into a subtree, we set the upper bound to the maximum of the current node's value and the new upper bound. Then, for each subsequent node, we check if their value is within the allowed range. If not, return false.

Yes, that makes sense. Let's see:

Define a helper function that takes a node and the lower and upper bounds. Initially, the bounds are [node.val]. Then, for each node, we update the bounds to be max(bounds[lower], node.val). Then, recursively check left and right. If any step fails, return false. Otherwise, return true.

This way, we avoid having to store all previous values. Instead, we only keep track of the allowed range. This reduces the space from O(n) to O(1), which is better.

So the steps would be:

Function isValidBST(node):

if node is null: return True

current_val = node.val

left_bounds = [current_val]

right_bounds = [current_val]

then call helper on left and right.

In helper:

if left is null: return True

if right is null: return True

if left.val > right.val: return False

return helper(left, left_bounds)

if right.val < left.val: return False

else:

update left_bounds to max(left_bounds[left], left.val)

update right_bounds to max(right_bounds[right], right.val)

call helper on left and right.

If all these checks pass, return True.

Wait, but what about the case where the left subtree has a higher value than the current node's value but the right subtree has a lower value? For example, left is 5, right is 3. Then 5>3, which violates the BST property. So the helper function will catch that.

Yes. So this logic works.

Now, handling the base cases. If the node is null, return true. Otherwise, proceed.

Testing some examples:

Test case 1: Single node. Valid. Returns true.

Test case 2: Root is 5, left is 3, right is 7. Left subtree is valid, right is invalid. So returns false.

Test case 3: Root is 5, left is 3, right is 5. Then left subtree is invalid

Sample 6

Prompt: Implement Dijkstra shortest path for a weighted directed graph represented as adjacency lists. Return distances from the source.

Output:

<think>
Okay, I need to implement Dijkstra's algorithm for a weighted directed graph using an adjacency list. Let me think about how to approach this.

First, I remember that Dijkstra's algorithm works by maintaining three main variables: distance to each node, a priority queue (or min-heap) to always pick the next node with the smallest tentative distance, and a visited array or set to keep track of nodes we've already processed. The key steps are:

1. Initialize all distances to infinity except the source node which is 0.
2. Use a priority queue to process nodes in order of their current known shortest distance.
3. For each node popped from the queue, check its neighbors. If a shorter path exists through the current node, update the neighbor's distance and add it to the priority queue if it hasn't been visited yet.
4. Continue until the queue is empty. If no more nodes can be processed, return a large number indicating unreachable sources.

But wait, since the problem says "return distances from the source," maybe there's a possibility that some nodes have zero distance? Or perhaps the input includes all possible nodes. Hmm, but the user didn't specify, so maybe I should assume that the graph has at least one node. But maybe not. So I should handle cases where the graph might have no edges, or nodes with zero weight.

Wait, the standard implementation uses a priority queue that starts with the source node. Then, when processing a node, you look at all its neighbors. For each neighbor, if the new distance (current distance + edge weight) is less than the stored distance, then update it and add to the queue.

So let's outline the steps again:

Initialize:
- dist array with all values set to infinity, except dist[source] = 0.
- Create a priority queue (min-heap) and push the source node into it.

Then, while the heap is not empty:
   - Pop the node with the smallest current distance.
   - If this node is visited before being added to the heap (i.e., if the distance stored in the heap is greater than the current node's distance), skip it.
   - Otherwise, process all its neighbors. For each neighbor:
      - Calculate the tentative distance (current node's distance + edge weight).
      - If this tentative distance is less than the neighbor's current distance, update the neighbor's distance and add it to the heap.

After processing all nodes, if the heap is exhausted (no more entries), return infinity or something indicating unreachable nodes. Wait, but the problem says "distance from the source." So if the graph is disconnected, the answer would be infinity. But maybe the problem expects us to return the minimum distance found, even if it's still infinity. Hmm, the question isn't clear on that. Let me re-read the problem statement.

The problem says "return distances from the source." So if there are multiple paths, which one do we choose? Probably, the first encountered shortest path. Because Dijkstra's algorithm ensures that once a node is popped from the priority queue, it's because the shortest path to it has been found. So even if there are multiple paths, the first one (the one with the smallest distance) will be processed first.

So the output should be the minimal distance among all reachable nodes. So if there are multiple nodes with the same minimal distance, we return the smallest one.

Now, implementing this in Python. Let's think about the data structures. The adjacency list can be a dictionary where each key is a node, and the value is a list of tuples representing the adjacent nodes and weights.

For example, adj = {
    'A': [('B', 5)],
    ...
}

Then, the priority queue can be implemented using heapq. Each time we pop a node from the heap, we check if the stored distance is larger than the current known distance. If yes, we skip processing it. Otherwise, we proceed.

In Python, the heapq module provides functions like heappop and heappush. So the steps would be:

import heapq

def dijkstra(graph, start):
    # Initialize distances
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))
    
    while heap:
        current_dist, u = heapq.heappop(heap)
        
        # Check if we've already found a better path to u
        if current_dist > dist[u]:
            continue
        
        for v, w in graph[u]:
            if dist[v] > current_dist + w:
                dist[v] = current_dist + w
                heapq.heappush(heap, (dist[v], v))
    
    # After processing all nodes, check if any nodes were unreachable
    # If the heap is empty, return infinity, else return the last element's distance
    if dist[-1] == float('inf'):
        return float('inf')
    else:
        return dist[-1]

Wait, but what if the graph is empty? Well, according to the problem statement, probably the graph is non-empty. But in practice, if the graph is empty, the function would return infinity. However, the problem may assume that the graph is connected. But the problem doesn't specify, so perhaps the code should handle that case.

Testing this code with sample inputs.

Sample Input 1:
graph = [
    ('A', 'B', 5),
    ('B', 'C', 3),
    ('C', 'D', 7),
    ('D', 'E', 8),
    ('E', 'F', 2),
    ('F', 'G', 10),
    ('G', 'H', 9)
]
start = 'A'

Expected Output: