# Coding Challenge #3

## Đề Bài

:::spoiler [Đề bài gốc](https://oj.vnoi.info/problem/coding_challenge_doxang) có thể được đọc trên hệ thống [VNOJ](https://oj.vnoi.info/contest/coding_challenge_3)
# **Coding Challenge #3 - Đổ Xăng**

Đổ Xăng

Vương quốc VNOI gồm $n$ thành phố được liên kết với nhau bằng $m$ con đường hai chiều, đảm bảo rằng mọi cặp thành phố đều có đường đi trực tiếp hoặc gián tiếp tới nhau. Con đường thứ $i$ kết nối hai thành phố $u_i, v_i$, và sẽ tốn $w_i$ lít xăng để đi qua.

Là một người đam mê du lịch, bạn lên kế hoạch cho chuyến đi chơi của mình tới VNOI. Bạn xuất phát từ thành phố $st$ và có dự định đi tới thành phố $en$ bằng xe của mình. Tất nhiên để đi xe thì phải tốn nhiên liệu, và xe của bạn có một bình chứa được tối đa $t$ lít xăng.

VNOI có $s$ trạm xăng. Trạm xăng thứ $i$ được phân bố ở thành phố $p_i$ và có chi phí cho mỗi lít xăng là $c_i$. Ở mỗi trạm xăng, bạn có thể mua không giới hạn số xăng (tất nhiên xe bạn chỉ mang tối đa được $t$ lít xăng thôi).

Bạn bắt đầu từ thành phố $st$ và xe bạn ban đầu không có xăng - may mắn rằng đảm bảo luôn có trạm xăng ở thành phố nơi bạn xuất phát. Hãy tính số tiền ít nhất cần bỏ ra để hoàn thành hành trình từ $st$ tới $en$.

## Input

- Dòng đầu gồm 3 số nguyên $n, m, s$ ($2 \le n \le 1000; 1 \le m \le 10^4; 1 \le s \le 100$)
- Dòng tiếp theo gồm một số nguyên dương $t$ ($1 \le t \le 10^5$) mô tả sức chứa của bình xăng.
- $m$ dòng tiếp theo, dòng thứ $i$ gồm ba số nguyên dương $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n; 1 \le w_i \le t$) miêu tả con đường thứ $i$.
- $s$ dòng tiếp theo, dòng thứ $i$ gồm hai số nguyên dương $p_i, c_i$ ($1 \le p_i \le n; 1 \le c_i \le 100$) miêu tả trạm xăng thứ $i$.
- Dòng cuối cùng gồm hai số nguyên dương $st, en$ ($1 \le st, en \le n$) miêu tả vị trí bắt đầu và đích đến của bạn.

## Output

- In ra số tiền ít nhất cần để đi chuyến đi.

## Subtask

- Subtask $1$ ($30$\%): $n \le 100$; $m \le 100$; $t \le 500$
- Subtask $2$ ($30$\%): $t \le 500$
- Subtask $3$ ($40$\%): Không giới hạn gì thêm.

## Sample Input 1

3 3 2
200
1 3 80
1 2 50
2 3 50
1 70
2 40
1 3

## Sample Output 1

5500

## Sample Input 2

5 5 3
100
1 2 80
2 5 80
1 3 40
3 4 60
4 5 60
1 8
2 9
3 2
1 5

## Sample Output 2

1340

## Sample Input 3

4 3 3
10
1 2 2
2 3 6
3 4 3
1 4
2 7
3 9
2 4

## Sample Output 3

61

:::

### Minh Họa Sample

:::spoiler Sample 1
:::

:::spoiler Sample 2
:::

:::spoiler Sample 3
:::

## Lời Giải

### [Subtask 1](https://hackmd.io/-MDkwOBIRzq-_VNYL00xcw#Subtask-1)

**Giới hạn:** $n \le 100$; $m \le 100$; $t \le 500$

#### Ý Tưởng

- Ta đặt $\text{costs}[i]$ là chi phí nhỏ nhất để mua $1$ lít xăng ở thành phố $i$.
Nếu thành phố thứ $i$ không có trạm xăng nào thì ta có thể coi $\text{cost}[i] = +\infty$.
- Ta có thể mô hình bài toán bằng cách dựng một đồ thị $G = (V, E)$ với mỗi đỉnh trong $G$ đại diện cho một trạng thái của xe, gồm:
- Thành phố xe đang dừng; và
- Lượng xăng xe đang có.
Nói cách khác, mỗi đỉnh có thể được biển diễn bằng một cặp số $(i, f)$ với $i$ là số hiệu thành phố và $f$ là lượng xăng hiện tại của xe ($1 \leq i \leq n$, $0 \leq f \leq t$).
- Ta sẽ có hai loại cạnh dựa trên hai loại hành động:
- Mua $1$ lít xăng: đồ thị chứa cạnh từ $(i, f)$ đến $(i, f + 1)$ (với điều kiện$f < t$) có trọng số $\text{costs}[i]$.
- Di chuyển sang thành phố khác trên con đường thứ $i$: đồ thị chứa cạnh từ $(u_i, r)$ đến $(v_i, r - w_i)$ (với điều kiện $r \geq w_i$) có trọng số $0$.
- Kết quả bài toán ta cần tìm lúc này sẽ tương đương với việc tìm độ dài của đường đi ngắn nhất từ đỉnh $(st, 0)$ đến một đỉnh $(en, f)$ bất kì với $0 \leq f \leq t$.
Vì mọi trọng số đều không âm, ta dùng [Dijkstra](https://wiki.vnoi.info/algo/graph-theory/shortest-path) để tìm được độ dài ấy.

#### Độ Phức Tạp

- Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian $O((|V| + |E|)\log |V|)$ nếu ta cài đặt thuật toán [Dijkstra](https://cp-algorithms.com/graph/dijkstra.html) với [heap](https://en.wikipedia.org/wiki/Heap_(data_structure)).
- Vì với mỗi thành phố, ta có $t + 1$ trạng thái khác nhau đại diện cho các mức xăng khác nhau, ta có $V = O(n \cdot t)$ .
- Vì với mỗi đường đi, ta sẽ có $O(t)$ cạnh loại thứ hai được nêu trên và với mỗi thành phố, ta sẽ có $O(t)$ cạnh loại thứ nhất được nếu trên, ta có $E = O((n + m) \cdot t)$.

#### Code Minh Họa

:::spoiler Code C++ minh họa

#include <bits/stdc++.h>
using namespace std;

template<class A, class B>
bool minimize(A &a, const B &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 1'003, MAX_S = 102, MAX_T = 1E5 + 5, INF = 0X3F3F3F3F;


vector<pair<int, int> > graph[MAX_N];
int n, m, s, t, st, en;
signed costs[MAX_N];

void input() {
    int u = 0, v = 0, w = 0, p = 0, c = 0;

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= n; ++i)
        costs[i] = INF;

    for (int e = 1; e <= m; ++e) {
        cin >> u >> v >> w;
        graph[u].emplace_back(w, v);
        graph[v].emplace_back(w, u);
    }

    for (int i = 1; i <= s; ++i) {
        cin >> p >> c;
        minimize(costs[p], c);
    }

    cin >> st >> en;
}

namespace Dijkstra {

    signed minimumCosts[MAX_N][MAX_T];
    priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > heap;

    void considerVertex(const int v, const int r, const int c) {
        if (minimize(minimumCosts[v][r], c))
            heap.emplace(c, make_pair(v, r));
    }

    void run() {
        memset(minimumCosts, INF, sizeof(minimumCosts));
        considerVertex(st, 0, 0);

        for (int x = 1; x <= n; ++x)
            sort(graph[x].begin(), graph[x].end());

        for (; !heap.empty();) {
            const auto [m, state] = heap.top();
            const auto &[x, r] = state;
            heap.pop();

            if (minimumCosts[x][r] != m)
                continue;

            if (x == en) {
                cout << m << '\n';
                return;
            }

            for (const auto &[w, y] : graph[x]) {
                if (r < w)
                    break;
                considerVertex(y, r - w, minimumCosts[x][r]);
            }

            if (r + 1 <= t)
                considerVertex(x, r + 1, minimumCosts[x][r] + costs[x]);
        }
    }

}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    Dijkstra::run();

    return 0;
}

:::

### [Subtask 2](https://hackmd.io/-MDkwOBIRzq-_VNYL00xcw#Subtask-2)

**Giới hạn:** $n \le 1000$; $m \le 10^4$; $t \le 500$

#### Ý Tưởng

- Vì chương trình giải cần phải chạy trong $1$ giây ([tương đương với khoảng $10^8$ lệnh](https://wiki.vnoi.info/algo/basic/computational-complexity.md)), giới hạn của [subtask 2](https://hackmd.io/-MDkwOBIRzq-_VNYL00xcw#Subtask-2) có thể khiến chương trình chạy quá thời gian khi sử dụng thuật toán [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) như trong [subtask 1](https://hackmd.io/-MDkwOBIRzq-_VNYL00xcw#Subtask-1).
Một thuật toán thay thế để tìm đường đi ngắn nhất ta có thể sử dụng để tìm đường đi ngắn nhất là [SPFA (Shortest Path Faster Algorithm)](https://cp-algorithms.com/graph/bellman_ford.html#shortest-path-faster-algorithm-spfa).

#### Độ Phức Tạp

- Trong trường hợp tệ nhất, chương trình cài đặt với [thuật toán SPFA](https://wiki.vnoi.info/algo/graph-theory/spfa) có thể đạt độ phức tạp thời gian $O(|V| \cdot |E|)$. Tuy nhiên, thời gian chạy trung bình của [SPFA](https://wiki.vnoi.info/algo/graph-theory/spfa) là rất nhanh, có thể được xem như thuật toán chạy với độ phức tạp $O(|E|)$ trong trường hợp này.

#### Code Minh Họa

:::spoiler Code C++ minh họa

#include <bits/stdc++.h>
using namespace std;

template<class A, class B>
bool minimize(A &a, const B &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 1'003, MAX_S = 102, MAX_T = 1E5 + 5, INF = 0X3F3F3F3F;


vector<pair<int, int> > graph[MAX_N];
int n, m, s, t, st, en;
signed costs[MAX_N];

void input() {
    int u = 0, v = 0, w = 0, p = 0, c = 0;

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= n; ++i)
        costs[i] = INF;

    for (int e = 1; e <= m; ++e) {
        cin >> u >> v >> w;
        graph[u].emplace_back(w, v);
        graph[v].emplace_back(w, u);
    }

    for (int i = 1; i <= s; ++i) {
        cin >> p >> c;
        minimize(costs[p], c);
    }

    cin >> st >> en;
}

namespace SPFA {

    signed minimumCosts[MAX_N][MAX_T];
    bool inqueue[MAX_N][MAX_T];
    queue<pair<int, int> > q;
    int result = INF;

    void considerVertex(const int v, const int r, const int c) {
        if (minimize(minimumCosts[v][r], c) && c < result) {
            if (v == en)
                minimize(result, c);
            if (!inqueue[v][r]) {
                q.emplace(v, r);
                inqueue[v][r] = true;
            }
        }
    }

    void run() {
        memset(minimumCosts, INF, sizeof(minimumCosts));
        considerVertex(st, 0, 0);

        for (int x = 1; x <= n; ++x)
            sort(graph[x].begin(), graph[x].end());

        for (; !q.empty(); q.pop()) {
            const auto &[x, r] = q.front();
            inqueue[x][r] = false;

            for (const auto &[w, y] : graph[x]) {
                if (r < w)
                    break;
                considerVertex(y, r - w, minimumCosts[x][r]);
            }

            if (r + 1 <= t)
                considerVertex(x, r + 1, minimumCosts[x][r] + costs[x]);
        }

        cout << result << '\n';
    }

}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    SPFA::run();

    return 0;
}

:::

### [Subtask 3](https://hackmd.io/-MDkwOBIRzq-_VNYL00xcw#Subtask-3)

**Giới hạn:** $n \le 1000$; $m \le 10^4$; $t \le 10^5$

#### Ý Tưởng

- Cách dựng đồ thị như trong hai Subtask đầu đều sẽ dẫn đến số lượng đỉnh và cạnh lớn trong [Subtask 3](https://hackmd.io/-MDkwOBIRzq-_VNYL00xcw#Subtask-3) (trong trường hợp tệ nhất, $|V|$ và $|E|$ có thể lần lượt đạt khoảng $10^8$ và hơn $10^9$).
- Tạm không xét đến chi tiết giá xăng, ta đặt $G_0 = (V_0, E_0)$ là đồ thị vô hướng có trọng số với mỗi đỉnh đại diện cho một thành phố và mỗi cạnh đại diện cho một đường đi ban đầu ($|V_0| = n$, $|E_0| = m$).
- Ta nhận thấy rằng không phải thành phố nào cũng có trạm xăng. Vì vậy để giảm số đỉnh cần xem xét, ta có thể mô hình bài toán theo một cách khác như sau:
Ta đặt $G_1 = (V_1, E_1)$ là một đầy đủ với:
- mỗi đỉnh đại diện cho một thành phố có trạm xăng hoặc là đich đến.
$\Rightarrow |V_1| = O(s)$
- mỗi cạnh có trọng số đại diện cho lượng xăng tối thiểu cần dùng để di chuyển giữa hai đỉnh nếu bình chứa là vô hạn (trọng số này tương đương với đường đi ngắn nhất trong $G_0$).
$\Rightarrow |E_1| = O(s^2)$
- Nếu ta xét thêm chi tiết giá xăng, ta có thể dựng một đồ thị $G' = (V', E')$ từ $G_1$ như cách ta có thể dựng đồ thị $G$ từ $G_0$ (bằng cách thêm chi tiết lượng xăng vào trạng thái, ...).
- Khi này, số lượng đỉnh tối đa sẽ được giảm xuống còn khoảng $10^7$ ($|V'| = O(s \cdot t)$).
- Tuy nhiên, số lượng cạnh vẫn quá lớn để xử lý ($|E'| = O(s^2 \cdot t)$ lớn hơn $10^9$)
- Để giảm số lượng cạnh cần xét, ta có một số nhận xét như sau:
Trong $G_1$, xét một cung từ $x$ tới $y$ với trọng số $w$,
- Nếu $\text{costs}[x] \geq \text{costs}[y]$ hoặc $y$ là đích đến thì trong $G'$, ngoại trừ **cạnh từ $(x, w)$ đến $(y, 0)$**, ta không cần phải xem xét bất kì cạnh nào khác giữa từ thành phố $x$ đến $y$.
:::spoiler Giải thích
Trong cả hai trường hợp, ta không có lý do để cần có nhiều hơn $w$ lít xăng ở thành phố $x$ bởi:
- Với trường hợp đầu, ta có thể mua xăng với giá rẻ hơn ở thành phố $y$ (nếu ta không mua xăng ở thành phố $y$ thì điều này đồng nghĩa với việc, ta muốn đến thành phố khác trong $V_1$ từ $x$).
- Với trường hợp sau, ta không đi thêm bất kì đâu khi đã đến đích.
:::
- Nếu $\text{costs}[x] < \text{costs}[y]$ thì trong $G'$, ngoại trừ **cạnh từ $(x, t)$ đến $(y, t - w)$**, ta không cần phải xem xét bất kì cạnh nào khác từ thành phố $x$ đến $y$.
:::spoiler Giải thích
Ta không có lý do để cần có ít hơn $t$ lít xăng ở thành phố $x$ bởi:
- Nếu ta không mua xăng ở thành phố $y$ thì điều này đồng nghĩa với việc, ta muốn đến thành phố khác trong $V_1$ từ $x$ (vì $G_1$ là một đồ thị đầy đủ được định nghĩa như trên).
- Nếu ta mua xăng ở thành phố $y$ nhưng lại rời thành phố $x$ với lượng xăng không đầy bình, chi phí sẽ không được tối ưu bởi thay vì mua $1$ lít xăng ở $y$, ta có thể làm điều tương tự với chi phí rẻ hơn ở thành phố $x$.
:::
- Với những nhất xét này, số lượng cạnh cần xét sẽ giảm xuống $|E_2| = O(s^2 + s \cdot t)$ bởi ta chỉ xét tối đa một cạnh giữa hai thành phố khác nhau trong $G_1$.
:::spoiler Mở rộng
Số lượng cạnh và đỉnh cần xét có thể tiếp tục được giảm xuống $O(s^2)$ bằng cách chỉ xét những đỉnh $(x, f)$ có tối thiểu một cạnh đến đỉnh đại diện cho một thành phố khác $x$.
:::

#### Độ Phức Tạp

- Để dựng được đồ thị $G_1$, ta có thể cài đặt bằng cách chạy thuật toán [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) nhiều lần với các thành phố có trạm xăng làm đỉnh nguồn. Vì vậy, bước này sẽ có độ phức tạp thời gian $O(s \cdot n \cdot \log (n + m))$.
- Nếu ta tiếp tục sử dụng [thuật toán SPFA](https://wiki.vnoi.info/algo/graph-theory/spfa) trên đồ thị $G_2 = (V_1, E_2)$, bước tìm kết quả cuối cùng sẽ có độ phức tạp $O(s^2 + s \cdot t)$.
Vì thế độ phức tạp tổng cho các bước xử lý chính có thể được xem như $O(s \cdot n \cdot \log(n + m) + s^2 + s \cdot t)$.

#### Code Minh Họa

:::spoiler Code C++ minh họa

#include <bits/stdc++.h>
using namespace std;

template<class A, class B>
bool minimize(A &a, const B &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 1'003, MAX_S = 102, MAX_T = 1E5 + 5, INF = 0X3F3F3F3F;

vector<pair<int, int> > graph[MAX_N];
long long minimumCost = INF;
int n, m, s, t, st, en;
signed costs[MAX_N];

void input() {
    int u = 0, v = 0, w = 0, p = 0, c = 0;

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= n; ++i)
        costs[i] = INF;

    for (int e = 1; e <= m; ++e) {
        cin >> u >> v >> w;
        graph[u].emplace_back(w, v);
        graph[v].emplace_back(w, u);
    }

    for (int i = 1; i <= s; ++i) {
        cin >> p >> c;
        minimize(costs[p], c);
        minimize(minimumCost, c);
    }

    cin >> st >> en;
}

namespace DijkstraAlgorithm {

    int vertexCount, vertexID[MAX_N], minimumDistances[MAX_S][MAX_S];
    vector<int> vertices, prices;

    void findMinimumDistances(const int source) {
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > heap;
        vector<int> distances(n + 1, INF);
        heap.emplace(distances[source] = 0, source);
        for (; !heap.empty();) {
            const auto [d, x] = heap.top();
            heap.pop();
            for (const auto &[w, y] : graph[x])
                if (minimize(distances[y], distances[x] + w))
                    heap.emplace(distances[y], y);
        }
        for (const int &destination : vertices)
            minimumDistances[vertexID[source]][vertexID[destination]] = distances[destination];
    }

    void run() {
        for (int i = 1; i <= n; ++i)
            if (costs[i] < INF || i == en) {
                vertexID[i] = (vertexCount++);
                vertices.push_back(i);
            } else
                vertexID[i] = -1;
        prices.resize(vertexCount);
        for (int i = 0; i < vertexCount; ++i) {
            findMinimumDistances(vertices[i]);
            prices[i] = costs[vertices[i]];
        }
    }

}

namespace SPFA {

    using namespace DijkstraAlgorithm;

    unordered_map<int, unordered_map<int, vector<int> > > graph;
    int endVertex, minimumCosts[MAX_S][MAX_T];
    bool inqueue[MAX_S][MAX_T];
    queue<pair<int, int> > q;
    int result = INF;

    void considerVertex(const int v, const int r, const int c) {
        if (minimize(minimumCosts[v][r], c) && c < result) {
            if (v == endVertex)
                result = c;
            else if (!inqueue[v][r]) {
                inqueue[v][r] = true;
                q.emplace(v, r);
            }
        }
    }

    void buildGraph() {
        endVertex = vertexID[en];
        for (int x = 0, y = 0; x < vertexCount; ++x)
            for (y = 0; y < vertexCount; ++y) {
                if (x == y || minimumDistances[x][y] > t)
                    continue;
                if (prices[x] >= prices[y] || y == endVertex) {
                    graph[x][minimumDistances[x][y]].push_back(y);
                    continue;
                }
                graph[x][t].push_back(y);
            }
    }

    void run() {
        buildGraph();
        memset(minimumCosts, INF, sizeof(minimumCosts));
        considerVertex(vertexID[st], 0, 0);

        for (; !q.empty(); q.pop()) {
            const auto &[x, r] = q.front();
            inqueue[x][r] = false;

            const auto outerElement = graph.find(x);

            if (outerElement != graph.end()) {
                const auto &innerElements = (outerElement -> second);
                const auto innerElement = innerElements.find(r);

                if (innerElement != innerElements.end()) {
                    for (const auto &y : (innerElement -> second))
                        considerVertex(y, r - minimumDistances[x][y], minimumCosts[x][r]);
                }
            }

            if (r + 1 <= t)
                considerVertex(x, r + 1, minimumCosts[x][r] + prices[x]);
        }

        cout << result << '\n';
    }

}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    DijkstraAlgorithm::run();
    SPFA::run();

    return 0;
}

:::