---
# System prepended metadata

title: Đường dẫn khí Solution
tags: [...]

---

---
author: little
tags: Đường dẫn khí
title: Đường dẫn khí Solution
---

$\Huge\text{Đường dẫn khí Solution}$

-------

:::info
📌 Tags: `dijkstra`   
✍️ Writer: little  
📋 Content:
[TOC]
:::
 
-----

## Thuật toán

Gọi $dist[u][k]$ là tổng số chi phí nhỏ nhất khi đi từ đỉnh $1$ đến đỉnh $u$ và đã sử dụng $k$ ống dẫn khí đốt.

Ta chuyển trạng thái như sau: 
```cpp=
if(dist[v][c] > dist[u][c] + cost[u][i]) {
    dist[v][c] = dist[u][c] + cost[u][i];
    pq.push({dist[v][c], {v, c}});
}

if(c + 1 <= k && dist[v][c + 1] > dist[u][c]) {
    dist[v][c + 1] = dist[u][c];
    pq.push({dist[v][c + 1], {v, c + 1}});
}
```

----

Tham khảo code ở [đây](https://ideone.com/vUtDS8)