제출 #964383

#제출 시각아이디문제언어결과실행 시간메모리
964383emad234사이버랜드 (APIO23_cyberland)C++17
8 / 100
1119 ms2097152 KiB
#include <bits/stdc++.h> #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 = 4e6 + 5; 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 solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { vector<vector<double>>dp; vector<int>vis; vector<vector<pii>> v; dp.resize(N + 3); vis.resize(N + 3); v.resize(N + 3); 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++){ dp[i].resize(K + 3); for(int j = 0;j <= K;j++){ dp[i][j] = 1e18; } } priority_queue<path,vector<path>,greater<path>>q; queue<int>bfs; bfs.push(0); q.push({0,0,0}); dp[0][0] = 0; while(bfs.size()){ auto u = bfs.front(); vis[u] = 1; bfs.pop(); if(arr[u] == 0) { q.push({u,0,0}); dp[u][0] = 0; } for(auto x : v[u]){ if(!vis[x.F]){ vis[x.F] = 1; bfs.push(x.F); } } } while(q.size()){ auto u = q.top(); q.pop(); if(u.val < dp[u.i][u.k]) continue; for(auto x : v[u.i]){ if(arr[x.F] == 0) continue; 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 = 1e18; for(int i = 0;i <= K;i++){ ans = min(ans,dp[H][i]); } return ans; } // int main() // { // 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)); // vector<int> x(M); // vector<int> y(M); // vector<int> c(M); // 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])); // 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...