#include<bits/stdc++.h>
using namespace std;
const double INF = 1e18;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
// Batasi penggunaan diskon
k = min(k, 100);
// Inisialisasi graf
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < m; i++) {
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
// Inisialisasi state
vector<double> dist(n, INF);
vector<double> temp(n, INF);
double ans = INF;
// Iterasi 0: tanpa diskon
temp[0] = 0.0;
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> pq;
pq.push({0.0, 0});
while (!pq.empty()) {
auto [cost, u] = pq.top();
pq.pop();
// Skip jika sudah ada cost yang lebih baik
if (abs(cost - temp[u]) > 1e-9) continue;
// Update jawaban jika mencapai tujuan
if (u == h) ans = min(ans, cost);
// Proses tetangga
for (auto [v, w] : adj[u]) {
double new_cost = cost + w;
// Penanganan khusus node tipe 0
if (a[v] == 0 && new_cost > 1e-9) new_cost = 0.0;
if (new_cost < temp[v]) {
temp[v] = new_cost;
pq.push({new_cost, v});
}
}
}
// Jika tidak ada jalur di iterasi 0
if (temp[h] >= INF) return -1.0;
// Update state untuk iterasi diskon
dist = temp;
ans = min(ans, dist[h]);
// Iterasi diskon (1 hingga k)
for (int j = 1; j <= k; j++) {
// Reset state sementara
fill(temp.begin(), temp.end(), INF);
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> pq;
// Inisialisasi dari state sebelumnya
for (int i = 0; i < n; i++) {
if (dist[i] >= INF) continue;
// Penanganan node khusus
if (a[i] == 0) {
temp[i] = 0.0;
pq.push({0.0, i});
} else if (a[i] == 2) {
double discounted = dist[i] / 2.0;
if (discounted < temp[i]) {
temp[i] = discounted;
pq.push({discounted, i});
}
}
}
// Jalankan Dijkstra
while (!pq.empty()) {
auto [cost, u] = pq.top();
pq.pop();
// Skip jika sudah ada cost yang lebih baik
if (abs(cost - temp[u]) > 1e-9) continue;
// Update jawaban jika mencapai tujuan
if (u == h) ans = min(ans, cost);
// Proses tetangga
for (auto [v, w] : adj[u]) {
double new_cost = cost + w;
// Penanganan khusus node tipe 0
if (a[v] == 0 && new_cost > 1e-9) new_cost = 0.0;
if (new_cost < temp[v]) {
temp[v] = new_cost;
pq.push({new_cost, v});
}
}
}
// Update state untuk iterasi berikutnya
dist = temp;
}
return (ans < INF - 1e9) ? ans : -1.0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |