#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) {
k = min(k, 100);
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]});
}
vector<double> dist(n, INF); // Lapisan sebelumnya
vector<double> temp(n, INF); // Lapisan saat ini
double ans = INF;
// Inisialisasi iterasi 0
temp[0] = 0.0;
for (int j = 0; j <= k; j++) {
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> pq;
// Inisialisasi priority queue
if (j == 0) {
// Iterasi pertama: mulai dari semua node yang sudah diakses
for (int i = 0; i < n; i++) {
if (temp[i] < INF) {
pq.push({temp[i], i});
}
}
} else {
// Iterasi diskon: mulai dari node khusus (tipe 0 atau 2)
for (int i = 0; i < n; i++) {
if (a[i] == 1) continue; // Skip node normal
if (dist[i] < INF) {
if (a[i] == 0) {
temp[i] = 0.0;
pq.push({0.0, i});
} else if (a[i] == 2) {
double new_cost = dist[i] / 2.0;
if (new_cost < temp[i]) {
temp[i] = new_cost;
pq.push({new_cost, i});
}
}
}
}
}
// Jalankan Dijkstra untuk lapisan saat ini
while (!pq.empty()) {
auto [cost, u] = pq.top();
pq.pop();
if (abs(cost - temp[u]) > 1e-9) continue; // Periksa presisi floating point
if (u == h) continue; // Tidak perlu proses node tujuan lebih lanjut
for (auto &[v, w] : adj[u]) {
double new_cost = cost + w;
// Update jalur normal
if (new_cost < temp[v]) {
temp[v] = new_cost;
// Handle node tipe 0
if (a[v] == 0) temp[v] = 0.0;
pq.push({temp[v], v});
}
}
}
// Update jawaban dengan nilai terbaik ke node h
ans = min(ans, temp[h]);
// Early termination jika tidak ada solusi di iterasi pertama
if (j == 0 && temp[h] >= INF) break;
// Siapkan untuk iterasi berikutnya
dist = temp;
fill(temp.begin(), temp.end(), INF);
}
return (ans < INF - 1e9) ? ans : -1.0; // Periksa dengan toleransi
}
# | 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... |