---
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:

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)