제출 #761030

#제출 시각아이디문제언어결과실행 시간메모리
761030aufan사이버랜드 (APIO23_cyberland)C++17
97 / 100
3073 ms94460 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; const double INFF = 1e18; double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { vector<vector<pair<int, double>>> v(n); for (int i = 0; i < m; i++) { v[x[i]].push_back({y[i], c[i]}); v[y[i]].push_back({x[i], c[i]}); } k = min(k, 70); vector<vector<double>> dist(n, vector<double>(k + 1, INFF)); priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> pq; vector<int> d(n, -1); d[0] = 1; queue<int> q; q.push(0); while (!q.empty()) { int x = q.front(); q.pop(); if (x == h) continue; for (auto [z, c] : v[x]) { if (d[z] == -1) { d[z] = 1; q.push(z); } } } for (int i = 0; i < n; i++) { if (d[i] == 1 && (arr[i] == 0 || i == 0)) { for (int ck = 0; ck <= k; ck++) { dist[i][ck] = 0; } pq.push({0, i, 0}); } } while (!pq.empty()) { auto [d, x, ck] = pq.top(); pq.pop(); if (dist[x][ck] < d || x == h) continue; for (auto [z, c] : v[x]) { if (arr[z] == 0 && 0 < dist[z][ck]) { dist[z][ck] = 0; pq.push({dist[z][ck], z, ck}); } if (arr[z] == 1 && d + c < dist[z][ck]) { dist[z][ck] = d + c; pq.push({dist[z][ck], z, ck}); } if (arr[z] == 2 && d + c < dist[z][ck]) { dist[z][ck] = d + c; pq.push({dist[z][ck], z, ck}); } if (ck < k && arr[z] == 2 && (d + c) / (double) (2) < dist[z][ck + 1]) { dist[z][ck + 1] = (d + c) / (double) (2); pq.push({dist[z][ck + 1], z, ck + 1}); } } } double ans = INFF; for (int ck = 0; ck <= k; ck++) ans = min(ans, dist[h][ck]); // loh bisa -1 return (ans == INFF ? -1 : ans); }
#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...