Submission #749421

#TimeUsernameProblemLanguageResultExecution timeMemory
749421Batorgil952Cyberland (APIO23_cyberland)C++17
97 / 100
3064 ms128848 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define ff first #define ss second using namespace std; const ll N=100005; vector< pair< ll, ll > > v[N]; double T[N][72]; bool B[N]; ll Ra[N]; void DFS(ll s, ll f){ Ra[s]=1; if(s==f) return; ll vn=v[s].size(); for(int i=0; i<vn; i++){ if(!B[v[s][i].ff]){ B[v[s][i].ff]=true; DFS(v[s][i].ff, f); } } return; } double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){ K=min(K, 70); for(ll i=0; i<N; i++){ Ra[i]=0; B[i]=false; v[i].clear(); } for(ll i=0; i<M; i++){ ll X=x[i], Y=y[i], Z=c[i]; v[X].pb(mp(Y, Z)); v[Y].pb(mp(X, Z)); } Ra[0]=1; B[0]=true; DFS(0, H); if(!Ra[H]) return -1; priority_queue< pair< double, pair< ll, ll > >, vector< pair< double, pair< ll, ll > > >, greater< pair< double, pair< ll, ll > > > > q; for(ll i=0; i<N; i++){ if(Ra[i] && !arr[i]){ q.push(mp(0.0, mp(0, i))); for(ll j=0; j<=70; j++){ T[i][j]=0.0; } } else if(i==0){ q.push(mp(0.0, mp(0, i))); for(ll j=0; j<=70; j++){ T[i][j]=0.0; } } else{ for(ll j=0; j<=70; j++){ T[i][j]=1000000000000000000.0; } } } while(!q.empty()){ double fx=q.top().ff; ll fy=q.top().ss.ff; ll fz=q.top().ss.ss; q.pop(); if(T[fz][fy]<fx){ continue; } if(fz==H){ continue; } ll vn=v[fz].size(); for(ll i=0; i<vn; i++){ double dd=v[fz][i].ss*1.0; double fare=fx+dd; if(arr[v[fz][i].ff]==1){ if(fare<T[v[fz][i].ff][fy]){ q.push(mp(fare, mp(fy, v[fz][i].ff))); T[v[fz][i].ff][fy]=fare; } } if(arr[v[fz][i].ff]==2){ if(fare<T[v[fz][i].ff][fy]){ q.push(mp(fare, mp(fy, v[fz][i].ff))); T[v[fz][i].ff][fy]=fare; } if(fy+1<=K && fare/2.0<T[v[fz][i].ff][fy+1]){ fare/=2.0; q.push(mp(fare, mp(fy+1, v[fz][i].ff))); T[v[fz][i].ff][fy+1]=fare; } } } } double ans=1000000000000000000.0; for(ll i=0; i<=K; i++){ ans=min(ans, T[H][i]); } 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...