Submission #1088941

#TimeUsernameProblemLanguageResultExecution timeMemory
1088941Math4Life2020Cyberland (APIO23_cyberland)C++17
42 / 100
3075 ms2097152 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll,ll>; using ld = long double; using vi = vector<int>; const ld INF = 1e18; double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) { ld tmin[N][K+1]; bool dfsf[N]; for (ll i=0;i<N;i++) { dfsf[i]=0; for (ll k=0;k<=K;k++) { tmin[i][k]=INF; } } vector<pii> adj[N]; //vertex,cost for (ll i=0;i<M;i++) { adj[x[i]].push_back({y[i],c[i]}); adj[y[i]].push_back({x[i],c[i]}); } stack<int> s; s.push(0); while (!s.empty()) { ll x = s.top(); s.pop(); if (!dfsf[x]) { dfsf[x]=1; for (pii p0: adj[x]) { s.push(p0.first); } } } if (!dfsf[H]) { return -1.0; } priority_queue<pair<ld,pii>> pq; //{time,{position, #k}} pq.push({0.0,{0,0}}); while (!pq.empty()) { auto A = pq.top(); pq.pop(); ld T = A.first; ll x = A.second.first; ll k = A.second.second; if (arr[x]==0) { T = 0.0; k = 0; } if (tmin[x][k]<=(T+1e-10)) { continue; } tmin[x][k]=min(tmin[x][k],T); if (x==H) { continue; } for (pii p0: adj[x]) { ll y = p0.first; ld ce = p0.second; pq.push({ce+T,{y,k}}); if (arr[x]==2 && k<K) { pq.push({ce+T/2,{y,k+1}}); } } } ld ans = INF; for (ll k=0;k<=K;k++) { ans = min(ans,tmin[H][k]); } if (ans == INF) { return -1.0; } else { return 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...