제출 #1009491

#제출 시각아이디문제언어결과실행 시간메모리
1009491Muaath_5사이버랜드 (APIO23_cyberland)C++17
97 / 100
3040 ms78504 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast,O3,unroll-loops") #pragma GCC target("avx2") #define all(v) ((v).begin(), (v).end()) #define F first #define S second typedef long long ll; #define pii pair<ll, double> using namespace std; const ll mod = 1e9 + 7; const ll mxN = 1e5 + 5; const double inf = 1e18; struct path { ll i, k; double val; }; bool operator<(path a, path b) { return a.val < b.val; } bool operator>(path a, path b) { return a.val > b.val; } double dp[mxN][71]; vector<vector<pii>> v; double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { v.clear(); v.resize(N + 3); K = min(K,70); for (int i = 0; i < M; i++) { v[x[i]].push_back({y[i], (double)c[i]}); v[y[i]].push_back({x[i], (double)c[i]}); } for(int i = 0;i < N;i++) for(int j = 0;j <= K;j++) dp[i][j] = inf; priority_queue<path,vector<path>,greater<path>>q; q.push({0,0,0}); dp[0][0] = 0; while(q.size()){ const auto u = q.top(); q.pop(); if(u.val < dp[u.i][u.k] || u.i == H) continue; for(const auto &x : v[u.i]){ if (arr[x.F] == 0 && dp[x.F][u.k] != (double)0) { dp[x.F][u.k] = (double)0; q.push({x.F, u.k, (double)0}); } if(dp[x.F][u.k] > dp[u.i][u.k] + x.S){ dp[x.F][u.k] = dp[u.i][u.k] + x.S; q.push({x.F,u.k,dp[x.F][u.k]}); } if(u.k != K && arr[u.i] == 2 && dp[x.F][u.k + 1] > dp[u.i][u.k] / 2 + x.S){ dp[x.F][u.k + 1] = dp[u.i][u.k] / 2 + x.S; q.push({x.F,u.k + 1,dp[x.F][u.k + 1]}); } } } double ans = inf; for(int i = 0;i <= K;i++){ ans = min(ans,dp[H][i]); } return ans == inf ? -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...