Untitled

Dưới đây là cách cài đặt thuật toán Dijkstra với việc sử dụng voucher giảm giá trong Java. Chúng ta sẽ sử dụng một lớp `PriorityQueue` để quản lý hàng đợi ưu tiên và một lớp `Pair` để lưu trữ các trạng thái `(chi phí, đỉnh hiện tại, số voucher còn lại)`.

### Mã nguồn Java

```java
import java.util.*;

public class DijkstraWithVouchers {
    static class Pair {
        int cost;
        int node;
        int vouchersLeft;

        Pair(int cost, int node, int vouchersLeft) {
            this.cost = cost;
            this.node = node;
            this.vouchersLeft = vouchersLeft;
        }
    }

    public static int dijkstraWithVouchers(Map<Integer, List<int[]>> graph, int start, int end, int M) {
        // PriorityQueue để quản lý hàng đợi ưu tiên
        PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.cost));
        pq.add(new Pair(0, start, M));

        // distances lưu chi phí tối ưu cho mỗi trạng thái (đỉnh, số voucher còn lại)
        Map<String, Integer> distances = new HashMap<>();
        distances.put(start + "," + M, 0);

        while (!pq.isEmpty()) {
            Pair current = pq.poll();
            int currentDistance = current.cost;
            int currentNode = current.node;
            int vouchersLeft = current.vouchersLeft;

            // Nếu đỉnh hiện tại là đích, trả về chi phí
            if (currentNode == end) {
                return currentDistance;
            }

            // Xét các đỉnh kề
            if (graph.containsKey(currentNode)) {
                for (int[] edge : graph.get(currentNode)) {
                    int neighbor = edge[0];
                    int weight = edge[1];

                    // Chi phí khi không sử dụng voucher
                    int newDistance = currentDistance + weight;
                    String state = neighbor + "," + vouchersLeft;
                    if (newDistance < distances.getOrDefault(state, Integer.MAX_VALUE)) {
                        distances.put(state, newDistance);
                        pq.add(new Pair(newDistance, neighbor, vouchersLeft));
                    }

                    // Chi phí khi sử dụng voucher (nếu còn voucher)
                    if (vouchersLeft > 0) {
                        int discountedWeight = weight / 2;
                        int newDistanceWithVoucher = currentDistance + discountedWeight;
                        String stateWithVoucher = neighbor + "," + (vouchersLeft - 1);
                        if (newDistanceWithVoucher < distances.getOrDefault(stateWithVoucher, Integer.MAX_VALUE)) {
                            distances.put(stateWithVoucher, newDistanceWithVoucher);
                            pq.add(new Pair(newDistanceWithVoucher, neighbor, vouchersLeft - 1));
                        }
                    }
                }
            }
        }

        // Nếu không có đường đi đến đích
        return Integer.MAX_VALUE;
    }

    public static void main(String[] args) {
        // Tạo đồ thị: graph[node] = danh sách các cạnh (đỉnh kề, trọng số)
        Map<Integer, List<int[]>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(new int[]{1, 2}, new int[]{2, 4}));
        graph.put(1, Arrays.asList(new int[]{2, 1}, new int[]{3, 7}));
        graph.put(2, Arrays.asList(new int[]{3, 3}));
        graph.put(3, Collections.emptyList());

        int start = 0;
        int end = 3;
        int M = 2;  // Số voucher

        int distance = dijkstraWithVouchers(graph, start, end, M);
        if (distance == Integer.MAX_VALUE) {
            System.out.println("Không có đường đi từ A đến B");
        } else {
            System.out.println("Chi phí đường đi ngắn nhất từ " + start + " đến " + end + " là " + distance);
        }
    }
}
```

### Giải thích mã nguồn

1. **Lớp `Pair`**: Được sử dụng để lưu trữ thông tin về chi phí, đỉnh hiện tại và số voucher còn lại trong hàng đợi ưu tiên.

2. **Hàm `dijkstraWithVouchers`**:
   - Khởi tạo hàng đợi ưu tiên với trạng thái ban đầu.
   - Sử dụng `HashMap` để lưu trữ chi phí tối ưu cho từng trạng thái `(đỉnh, số voucher)`.
   - Xử lý các đỉnh kề, cập nhật chi phí cho cả hai trường hợp: sử dụng và không sử dụng voucher.

3. **Hàm `main`**:
   - Tạo đồ thị dưới dạng `HashMap` với danh sách các đỉnh kề và trọng số của các cạnh.
   - Gọi hàm `dijkstraWithVouchers` để tính chi phí tối ưu và in kết quả.

Chương trình này giúp tìm đường đi ngắn nhất từ điểm bắt đầu đến điểm kết thúc trong đồ thị có thể sử dụng voucher giảm giá.