Hướng dẫn giải của Đường đi săn sale
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
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;
}
Bình luận