# Solution — Lễ hội 3
## Lưu ý
**Chỉ đọc khi thật sự bí ý tưởng.**
---
# Tóm tắt bài toán
Ta có:
* $n$ địa điểm
* $m$ con đường hai chiều
Mỗi cạnh $u \leftrightarrow v$ có chi phí đi **lần đầu** là $w$.
Nếu đi qua cạnh đó **từ lần thứ hai trở đi**, chi phí sẽ là **0**.
Mỗi địa điểm $i$ bán rượu với giá:
$$
c_i
$$
Marisa:
1. xuất phát từ địa điểm $1$
2. đi đến **một địa điểm bất kỳ để mua rượu**
3. sau đó đi đến đền Hakurei ở địa điểm $n$
Mục tiêu là **tối thiểu hóa tổng chi phí**.
---
# Nhận xét quan trọng
Giả sử Marisa **mua rượu tại đỉnh $k$**.
Hành trình sẽ gồm hai phần:
### phần 1: đi từ nhà tới nơi mua
$$
1 \rightarrow k
$$
chi phí là:
$$
dist_1[k]
$$
---
### phần 2: đi từ nơi mua tới đền
$$
k \rightarrow n
$$
chi phí là:
$$
dist_N[k]
$$
---
### chi phí mua rượu
tại đỉnh $k$:
$$
c_k
$$
---
Nếu mua tại đúng đỉnh $k$ thì chi phí là:
$$
dist_1[k] + dist_N[k] + c_k
$$
Tuy nhiên bài toán cho phép **tận dụng việc đi lại miễn phí các cạnh đã đi**.
Điều này khiến việc chọn **mua ở một đỉnh khác rồi mang rượu đến $k$** có thể rẻ hơn.
---
# Ý tưởng chính
Ta muốn biết:
> chi phí rẻ nhất để **có rượu tại đỉnh $k$**
Không nhất thiết phải mua **ngay tại $k$**.
Ta có thể:
* mua ở đỉnh $i$
* sau đó mang rượu đến $k$
Chi phí khi đó là:
$$
c_i + dist(i,k)
$$
Do đó ta định nghĩa:
$$
f[k] = \min_{i} (c_i + dist(i,k))
$$
$f[k]$ là **chi phí rẻ nhất để có rượu tại $k$**.
---
# Tính $f[k]$ bằng Dijkstra
Ta coi mỗi đỉnh $i$ là một **nguồn ban đầu** với khoảng cách:
$$
dist[i] = c_i
$$
Sau đó chạy **Dijkstra đa nguồn**.
Khi đó:
$$
f[k] = \min_i (c_i + dist(i,k))
$$
Điều này được làm với hàm `dijkstra_multi()` trong code. =))
---
# Các bước của thuật toán
## Bước 1 — Dijkstra từ 1
Tính:
$$
d1[i] = dist(1,i)
$$
---
## Bước 2 — Dijkstra từ n
Tính:
$$
dN[i] = dist(n,i)
$$
---
## Bước 3 — Multi-source Dijkstra
Khởi tạo:
$$
f[i] = c_i
$$
và chạy Dijkstra để lan truyền chi phí rượu.
Sau bước này:
$$
f[i] = \min_j (c_j + dist(j,i))
$$
---
# Tính kết quả
Ta xét tất cả các đỉnh $k$:
$$
ans = \min_{k=1}^{n} (d1[k] + dN[k] + f[k])
$$
Trong đó:
* $d1[k]$ là chi phí từ nhà đến $k$
* $dN[k]$ là chi phí từ $k$ đến đền
* $f[k]$ là chi phí rẻ nhất để có rượu tại $k$
---
# Độ phức tạp
Chạy 3 lần Dijkstra:
$$
O((n+m)\log n)
$$
Với:
$$
n,m \le 10^5
$$
nên hoàn toàn phù hợp.
---
# Liên hệ với code
Ba hàm trong code tương ứng:
### `dijkstra1()`
tính:
$$
d1[i]
$$
---
### `dijkstra2()`
tính:
$$
dN[i]
$$
---
### `dijkstra_multi()`
tính:
$$
f[i]
$$
---
Cuối cùng:
```cpp
res = min(res, d1[k] + dN[k] + f[k]);
```
tương ứng với công thức:
$$
\min_{k=1}^{n} (d1[k] + dN[k] + f[k])
$$
## 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: 10:35:06 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 c[MAXN + 5], d1[MAXN + 5], dN[MAXN + 5], f[MAXN + 5];
vpii g[MAXN + 5];
void dijkstra1()
{
for(int i = 1; i <= n; i++) d1[i] = OO;
d1[1] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, 1});
while(!pq.empty())
{
int u = pq.top().se, du = pq.top().fi;
pq.pop();
if(du > d1[u]) continue;
for(auto &node : g[u])
{
int v = node.fi, w = node.se;
if(d1[v] > d1[u] + w)
{
d1[v] = d1[u] + w;
pq.push({d1[v], v});
}
}
}
}
void dijkstra2()
{
for(int i = 1; i <= n; i++) dN[i] = OO;
dN[n] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, n});
while(!pq.empty())
{
int u = pq.top().se, du = pq.top().fi;
pq.pop();
if(du > dN[u]) continue;
for(auto &node : g[u])
{
int v = node.fi, w = node.se;
if(dN[v] > dN[u] + w)
{
dN[v] = dN[u] + w;
pq.push({dN[v], v});
}
}
}
}
void dijkstra_multi()
{
for(int i = 1; i <= n; i++) f[i] = OO;
priority_queue<pii> pq;
for(int i = 1; i <= n; i++)
{
f[i] = c[i];
pq.push({-f[i], i});
}
while(!pq.empty())
{
int u = pq.top().se, fu = pq.top().fi; pq.pop();
fu = -fu;
if(fu > f[u]) continue;
for(auto &node : g[u])
{
int v = node.fi, w = node.se;
if(f[v] > f[u] + w)
{
f[v] = f[u] + w;
pq.push({-f[v], v});
}
}
}
}
_______TOISETHIVOI_______
{
fast;
if (FILE *f_ptr = fopen(NAME ".inp", "r")) {
fclose(f_ptr);
freopen(NAME ".inp", "r", stdin);
freopen(NAME ".out", "w", stdout);
}
cin>>n>>m;
for(int i = 1; i <= n; i++) cin >> c[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});
}
dijkstra1();
dijkstra2();
dijkstra_multi();
int res = OO;
for(int k = 1; k <= n; k++)
{
if(d1[k] != OO && dN[k] != OO && f[k] != OO)
{
res = min(res, d1[k] + dN[k] + f[k]);
}
}
cout << res << endl;
return 0;
}
```
Phatgivp10
Created at
1 likes