Submission #981844

#TimeUsernameProblemLanguageResultExecution timeMemory
9818448pete8사이버랜드 (APIO23_cyberland)C++17
97 / 100
3055 ms184984 KiB
#include "cyberland.h" #include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<unordered_map> #include <queue> #include<cstring> #include<limits.h> #include <cassert> #include<cmath> #include<set> #include<algorithm> #include <iomanip> #include<numeric> //gcd(a,b) #include<bitset> #include <cstdlib> #include <cstdint> using namespace std; #define ll long long #define f first //#define endl "\n" #define s second #define pii pair<int,int> #define ppii pair<int,pii> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; #define int long long //#define double long double const int inf=1e18,mxn=1e5; double pre=1e-7; struct info{ double cost; int cur,use,bro; bool operator<(info a)const{return (cost>a.cost);}; }; vector<pii>adj[mxn+10]; double what[mxn+10][70][2]; int p[mxn+10]; int find(int u){return (p[u]==u)?u:p[u]=find(p[u]);} priority_queue<info>pq; double_t solve(int32_t n,int32_t m,int32_t k,int32_t H,vector<int32_t>x,vector<int32_t>y,vector<int32_t>c,vector<int32_t> arr){ k=min(k,69); for(int i=0;i<n;i++)adj[i].clear(),p[i]=i; for(int i=0;i<m;i++){ adj[x[i]].pb({y[i],c[i]}); adj[y[i]].pb({x[i],c[i]}); // p[find(x[i])]=find(y[i]); } adj[H].clear(); for(int i=0;i<n;i++)for(int j=0;j<=k;j++)for(int g=0;g<2;g++)what[i][j][g]=inf; //for(int i=0;i<n;i++)if(arr[i]==0&&find(0)==find(i))pq.push({0,i,0,0}); what[0][0][0]=0; pq.push({0,0,0,0}); double ans=inf; while(!pq.empty()){ int cur=pq.top().cur,use=pq.top().use,bro=pq.top().bro; double cost=pq.top().cost; pq.pop(); if(what[cur][use][bro]<cost)continue; if(cur==H)ans=min(ans,cost); if(arr[cur]==2&&use<k&&bro==0){ if(what[cur][use+1][1]>(cost*1.0)/2){ what[cur][use+1][1]=(cost*1.0)/2;; pq.push((info){what[cur][use+1][1],cur,use+1,1}); } } for(auto i:adj[cur]){ if(what[cur][use][bro]+i.s<what[i.f][use][0]){ what[i.f][use][0]=cost+i.s; if(arr[i.f]==0)what[i.f][use][0]=0; pq.push((info){what[i.f][use][0]*1.0,i.f,use,0}); } } } if(ans==inf)return -1; return ans; } #undef int /* int32_t main(){ int t;cin>>t; int n,m,k,h;cin>>n>>m>>k>>h; vector<int>x(m),y(m),z(m),arr(n); for(int i=0;i<n;i++)cin>>arr[i]; for(int i=0;i<m;i++)cin>>x[i]>>y[i]>>z[i]; cout<<solve(n,m,k,h,x,y,z,arr); }*/ /* 1 4 4 30 3 1 1 2 1 0 1 5 0 2 4 1 3 2 2 3 4 */
#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...