Editorial for Đường đi săn sale
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
Ta duyệt qua mỗi cạnh trong dồ thị, thử loại cạnh đó ra khỏi đồ thị rồi Dijkstra tìm đường đi ngắn nhất. Độ phức tạp ~O(m^2logn)~.
Subtask 2
Vì không có vé VIP nào, bài toán trở thành bài toán tìm đường đi ngắn nhất. Ta áp dụng trực tiếp thuật toán Dijkstra. Độ phức tạp ~O(mlogn)~.
Subtask 3 và 4
Ta dựng một đồ thị mới, ta xem một trạng thái ~(node, used)~ là một đỉnh của đồ thị (~node~ là đỉnh hiện tại của Pusheen, ~used~ là số vé VIP đã sử dụng). Với mỗi đỉnh ~(node, used)~, ta có các loại cạnh sau:
- Trường hợp không sử dụng vé VIP: ~(node, used) \to (nextNode, used)~ với ~nextNode~ là đỉnh kề ~node~ trong đồ thị gốc. Trọng số của cạnh này bằng trọng số của cạnh ~node \to nextNode~ trong đồ thị gốc.
- Trường hợp sử dụng vé VIP: ~(node, used) \to (nextNode, used+1)~ với điều kiện ~used \le k~. Trọng số của cạnh này là ~0~, vì Pusheen đã sử dụng một vé VIP nên không mất tiền khi đi qua con dường đó.
Như vậy kết quả bài toán là đường đi ngắn nhất từ ~(s, 0)~ cho tới ~(t, x)~ ~(0 \le x \le k)~.
Code tham khảo:
// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;
/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
bool maximize(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
/***End of Template***/
int n, m, k, s, t;
const int N = 1e5+5;
vector<ii> adj[N];
ll dist[N][6];
void Input() {
cin >> n >> m >> k >> s >> t;
FOR(_, 1, m) {
int u, v, c; cin >> u >> v >> c;
adj[u].pb(mp(v, c));
adj[v].pb(mp(u, c));
}
}
void Solve() {
memset(dist, 0x3f, sizeof dist);
priority_queue<pair<ll, ii>> q;
dist[s][0] = 0;
q.push(mp(0, mp(s, 0)));
ll ans = 1e18;
while (q.size()) {
int u, c; tie(u, c) = q.top().se;
ll d = -q.top().fi; q.pop();
if (d != dist[u][c]) continue;
if (u == t) minimize(ans, d);
for(auto &e : adj[u]) {
if (minimize(dist[e.fi][c], dist[u][c] + e.se)) q.push(mp(-dist[e.fi][c], mp(e.fi, c)));
if (c < k && minimize(dist[e.fi][c+1], dist[u][c]))
q.push(mp(-dist[e.fi][c+1], mp(e.fi, c+1)));
}
}
cout << ans;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
Input(), Solve();
return 0;
}
Comments