Submission #1253881

#TimeUsernameProblemLanguageResultExecution timeMemory
1253881anfiCyberland (APIO23_cyberland)C++20
15 / 100
328 ms7996 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...