Submission #1253879

#TimeUsernameProblemLanguageResultExecution timeMemory
1253879anfiCyberland (APIO23_cyberland)C++20
44 / 100
93 ms8516 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) { 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 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...