# Solution — Chênh lệch giá
## Lưu ý
**Chỉ đọc khi thật sự bí ý tưởng.**
---
# Tóm tắt bài toán
Ta có đồ thị gồm $n$ thành phố và $m$ con đường hai chiều. Mỗi cạnh có chi phí di chuyển.
Mỗi thành phố $i$ có giá vàng $a_i$ . Trong suốt hành trình từ thành phố $1$ đến thành phố $n$, ta được phép thực hiện **tối đa một giao dịch vàng**:
* mua vàng ở thành phố $k$ với giá $a_k$
* bán vàng ở thành phố $p$ với giá $a_p$
Lợi nhuận khi giao dịch là:
$$
profit = a_p - a_k
$$
Do đó chi phí thực sự của hành trình sẽ là:
$$
cost_{path} - profit
$$
Ta cần tìm **chi phí nhỏ nhất để đi từ (1 \to n)**.
Lưu ý: kết quả có thể **âm**.
---
# Nhận xét
Trong quá trình đi từ $1$ tới $n$, trạng thái của ta liên quan đến việc giao dịch vàng. Có ba trạng thái:
1. **Chưa mua vàng**
2. **Đang cầm vàng (đã mua nhưng chưa bán)**
3. **Đã bán vàng**
Ta mô hình hóa bằng cách **tách mỗi đỉnh thành 3 tầng**.
---
# Xây dựng đồ thị 3 tầng
Ta tạo đồ thị với **$3n$ đỉnh**:
### Tầng 1
Các đỉnh:
$$
1 \dots n
$$
Trạng thái: **chưa mua vàng**
---
### Tầng 2
$$
n+1 \dots 2n
$$
Trạng thái: **đang cầm vàng**
---
### Tầng 3
$$
2n+1 \dots 3n
$$
Trạng thái: **đã bán vàng**
---
# Các cạnh di chuyển
Nếu tồn tại cạnh:
$$
u \leftrightarrow v
$$
có chi phí $w$, thì ở **mỗi tầng** đều tồn tại cạnh tương tự:
* $u \to v$ với chi phí $w$
* $v \to u$ với chi phí $w$
Cụ thể:
* tầng 1: $u \to v$
* tầng 2: $u+n \to v+n$
* tầng 3: $u+2n \to v+2n$
---
# Các cạnh giao dịch vàng
### Mua vàng
Khi đang ở thành phố $i$, nếu quyết định **mua vàng**, ta chuyển trạng thái:
* từ **chưa mua** → **đang cầm vàng**
$$
i \to i+n
$$
chi phí:
$$
+a_i
$$
---
### Bán vàng
Nếu đang cầm vàng tại thành phố $i$, ta có thể **bán vàng**:
* từ **đang cầm vàng** → **đã bán**
$$
i+n \to i+2n
$$
chi phí:
$$
-a_i
$$
Dấu âm thể hiện **thu lại tiền**.
---
# Điểm bắt đầu và kết thúc
* Bắt đầu tại **đỉnh $1$** (tầng 1)
* Kết thúc có thể là:
* $n$ chưa giao dịch
* $3n$ đã bán vàng
Vì vậy kết quả là:
$$
\min(d[n], d[3n])
$$
---
# Thuật toán
Sau khi xây dựng đồ thị $3n$ đỉnh, ta chỉ cần chạy:
**Dijkstra từ đỉnh 1**
Độ phức tạp:
$$
O((n+m)\log n)
$$
---
# Code mẫu
```cpp
/*
======================================================================================
Deep rivers flow quietly; ripe rice bows low.
Being a good software engineer is 3% talent, 97% not being distracted by the internet.
Author: duxp
Date created: 17:42:16 14/03/2026
___ ______
/ \ / |
/ ^ \ | ,----'
/ /_\ \ | |
/ _____ \ | `----.
/__/ \__\ \______|
*///=================================================================================||
#include<bits/stdc++.h>// ||
using namespace std;// ||
#define ll long long// ||
#define pb push_back// ||
#define all(x) x.begin() + 1, x.end()// ||
#define nall(x) x.begin(), x.end()// ||
#define vi vector<int>// ||
#define vpii vector<pair<int,int>>// ||
#define pll pair<ll, ll>// ||
#define pii pair<int, int>// ||
#define fi first// ||
#define endl '\n'// ||
#define se second// ||
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);// ||
#define mem(a, x) memset(a, x, sizeof(a))// ||
#define working cerr<<"If u see this message, your code is working orz "<<endl;// ||
#define trailingzero(x) __builtin_ctzll(x)// ||
#define cntbit1(x) __builtin_popcountll(x)// ||
#define leadingzero(x) __builtin_clzll(x)// ||
#define _______TOISETHIVOI_______ signed main()// ||
#define KILL() exit(0)// ||
#define NAME "duxp"// ||
//=====================================================================================
template <typename T> // ||
inline int getbit(T x, int k) { return (x >> k) & 1; }// ||
template <typename T>// ||
inline T onbit(T x, int k) { return x | (T(1) << k); }// ||
template <typename T>// ||
inline T offbit(T x, int k) { return x & ~(T(1) << k); }// ||
//=====================================================================================
const ll OO = 1e18;// ||
const int oo = 1e9;// ||
const int MOD = 1000000007;// ||
const int MOD2 = 998244353;// ||
const int MAXN = 200000;// ||
//================================
#define int ll
int n, m;
int a[MAXN + 5];
vpii g[3 * MAXN + 5];
int d[3 * MAXN + 5];
void dijkstra(int s)
{
fill(d, d + 3 * MAXN + 4, OO);
d[s] = 0;
priority_queue<pii> pq;
pq.push({0, s});
while(!pq.empty())
{
pii curr = pq.top(); pq.pop();
int du = curr.fi, u = curr.se;
if(-du > d[u]) continue;
for(auto &node : g[u])
{
int v = node.fi, w = node.se;
if(d[v] > d[u] + w)
{
d[v] = d[u] + w;
pq.push({-d[v], v});
}
}
}
}
_______TOISETHIVOI_______
{
fast;
if (FILE *f = fopen(NAME ".inp", "r")) {
fclose(f);
freopen(NAME ".inp", "r", stdin);
freopen(NAME ".out", "w", stdout);
}
cin>>n>>m;
for(int i = 1; i <= n; i++) cin>>a[i];
for(int i = 1; i <= m; i++)
int u,v,w; cin>>u>>v>>w;
g[u].pb({v, w});
g[v].pb({u, w});
// n
g[u + n].pb({v + n, w});
g[v + n].pb({u + n, w});
// 2n
g[u + 2 * n].pb({v + 2 * n, w});
g[v + 2 * n].pb({u + 2 * n, w});
}
for(int i = 1; i <= n; i++)
{
g[i].pb({i + n, a[i]});
g[i + n].pb({i + 2 * n, -a[i]});
}
dijkstra(1);
cout<<min(d[n], d[3 * n]);
}
```
Phatgivp10
Created at
1 likes