제출 #969396

#제출 시각아이디문제언어결과실행 시간메모리
969396CDuong사이버랜드 (APIO23_cyberland)C++17
97 / 100
3047 ms96324 KiB
#include <bits/stdc++.h> #include "cyberland.h" #define i64 long long #define ff first #define ss second using namespace std; double solve(int n, int m, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { K = min(K, 75); vector<vector<int>> G(n); for (int i = 0; i < m; ++i) { G[x[i]].emplace_back(i); G[y[i]].emplace_back(i); } // cout << n << " " << m << endl; vector<vector<double>> dis(n, vector<double>(K + 1, 1e18)); priority_queue<pair<double, pair<int, int>>, vector<pair<double, pair<int, int>>>, greater<pair<double, pair<int, int>>>> pq; dis[0][0] = 0; pq.emplace(0, pair(0, 0)); while (not pq.empty()) { auto w = pq.top().ff; auto v = pq.top().ss.ff; auto used = pq.top().ss.ss; pq.pop(); // cout << w << " " << v << " " << used << endl; if (w != dis[v][used]) continue; if (v == H) continue; double nw; for (int eidx : G[v]) { int u = x[eidx] ^ y[eidx] ^ v; if (arr[u] == 0) { nw = 0; if (dis[u][used] > nw) { dis[u][used] = nw; pq.emplace(nw, pair(u, used)); } } if (arr[u] == 2 and used < K) { nw = (w + c[eidx]) / 2; if (dis[u][used + 1] > nw) { dis[u][used + 1] = nw; pq.emplace(nw, pair(u, used + 1)); } } nw = w + c[eidx]; if (dis[u][used] > nw) { dis[u][used] = nw; pq.emplace(nw, pair(u, used)); } } } double res = 1e18; for (int i = 0; i <= K; ++i) res = min(res, dis[H][i]); return (res == 1e18 ? -1 : res); } // int main() { // freopen("bai3.inp", "r", stdin); // freopen("bai3.out", "w", stdout); // int T; // assert(1 == scanf("%d", &T)); // while (T--){ // int N,M,K,H; // assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H)); // std::vector<int> x(M); // std::vector<int> y(M); // std::vector<int> c(M); // std::vector<int> arr(N); // for (int i = 0; i < N; i++) assert(1 == scanf("%d", &arr[i])); // for (int i = 0; i < M; i++) assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i])); // // if (T == 10000 - 195) { // // cout << N << " " << M << " " << K << " " << H << endl; // // for (int i = 0; i < N; ++i) cout << arr[i] << " \n"[i + 1 == N]; // // for (int i = 0; i < M; ++i) cout << x[i] << " " << y[i] << " " << c[i] << "\n"; // // } // printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr)); // } // }
#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...