제출 #841018

#제출 시각아이디문제언어결과실행 시간메모리
841018GoldLight사이버랜드 (APIO23_cyberland)C++17
39 / 100
531 ms67596 KiB
#include <bits/stdc++.h> using namespace std; void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);} const int N=1e5; const double INF=1e16; vector<pair<int,int>> v[N+1]; priority_queue<array<double,4>, vector<array<double,4>>, greater<array<double,4>>> pq; double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a){ for(int i=0; i<n; i++) v[i].clear(); for(int i=0; i<m; i++){ v[x[i]].push_back({y[i], c[i]}); v[y[i]].push_back({x[i], c[i]}); } k=min(k, 70); // set<int> t; // vector<bool> vis(n); // queue<int> q; // q.push(0); // vis[0]=true; // while(!q.empty()){ // int u=q.front(); q.pop(); // if(u==h) continue; // for(auto [p, q1]:v[u]){ // if(vis[p]) continue; // if(a[p]==0) t.insert(p); // q.push(p); // vis[p]=true; // } // } double pw[k+1]; pw[0]=1.0; for(int i=1; i<=k; i++) pw[i]=pw[i-1]*2; vector<vector<double>> dp(n, vector<double>(k+1, INF)); for(int i=0; i<=k; i++) dp[h][i]=0; pq.push({0, h, 0, 0}); double ans=INF; while(!pq.empty()){ double d=pq.top()[0]; int u=pq.top()[1], dis=pq.top()[2], nol=pq.top()[3]; pq.pop(); if(d>dp[u][dis]) continue; for(auto [to, dist]:v[u]){ if(nol && d<dp[to][dis]){ dp[to][dis]=d; pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2)), nol}); } if(d+dist/pw[dis]<dp[to][dis]){ dp[to][dis]=d+dist/pw[dis]; pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2)), nol|(a[to]==0)}); } } } for(int i=0; i<=k; i++) ans=min(ans, dp[0][i]); if(ans==INF) return -1; return ans; } /* int main(){ fast(); int n, m, k, h; cin>>n>>m>>k>>h; vector<int> x(N+1), y(N+1), c(N+1), a(N+1); for(int i=0; i<m; i++){ cin>>x[i]>>y[i]>>c[i]; } for(int i=0; i<n; i++) cin>>a[i]; cout<<solve(n, m, k, h, x, y, c, a); } */ /* const int N=1e5; const double INF=1e16; int n, m, k, h; vector<pair<int,int>> v[N+1], ad; //adventure graph vector<int> a; bool f=false; //find cyberland void dfs(int node, int p){ if(f) return; for(auto [i, d]:v[node]){ if(i==p) continue; int di=0; if(a[i]!=0) di=d; ad.push_back({di, a[i]}); if(i==h) f=true; dfs(i, node); } if(f) return; ad.pop_back(); } priority_queue<tuple<double,int,int>, vector<tuple<double,int,int>>, greater<tuple<double,int,int>>> pq; double solve(int nn, int mm, int kk, int hh, vector<int> x, vector<int> y, vector<int> c, vector<int> aa){ for(int i=0; i<n; i++) v[i].clear(); n=nn, m=mm, k=kk, h=hh, a=aa; for(int i=0; i<m; i++){ v[x[i]].push_back({y[i], c[i]}); v[y[i]].push_back({x[i], c[i]}); } // if(m==n-1){ // ad.clear(); // dfs(0, -1); // priority_queue<int> pqq; // double ans=0; // for(auto [p, q]:ad){ // if(q==2) pqq.push(p); // else ans+=p; // } // while(!pqq.empty()){ // int u=pqq.top(); pqq.pop(); // if(k) ans+=double(u)/2; // else ans+=u; // k--; // } // return ans; // } vector<vector<double>> dp(n+1, vector<double>(k+1, INF)); dp[0][0]=0; pq.push({0, 0, 0}); //dist, node now, disc while(!pq.empty()){ auto[d, u, dis]=pq.top(); pq.pop(); if(d>dp[u][dis]) continue; for(auto [to, dist]:v[u]){ if(a[to]==0){ if(0<dp[to][dis]){ dp[to][dis]=0; pq.push({0, to, dis}); } } else if(a[to]==1){ if(d+dist<dp[to][dis]){ dp[to][dis]=d+dist; pq.push({dp[to][dis], to, dis}); } } else{ if(d+dist<dp[to][dis]){ dp[to][dis]=d+dist; pq.push({dp[to][dis], to, dis}); } if(dis<k && d+dist/2<dp[to][dis+1]){ dp[to][dis+1]=d+dist/2; pq.push({dp[to][dis+1], to, dis+1}); } } } } double ans=INF; for(int i=0; i<=k; i++) ans=min(ans, dp[h][i]); if(ans==INF) return -1; else return ans; } */ /* int main(){ fast(); int n, m, k, h; cin>>n>>m>>k>>h; vector<int> x(N+1), y(N+1), c(N+1), a(N+1); for(int i=0; i<m; i++){ cin>>x[i]>>y[i]>>c[i]; } for(int i=0; i<n; i++) cin>>a[i]; cout<<solve(n, m, k, h, x, y, c, a); } */

컴파일 시 표준 에러 (stderr) 메시지

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:36:14: warning: narrowing conversion of 'h' from 'int' to 'double' [-Wnarrowing]
   36 |  pq.push({0, h, 0, 0});
      |              ^
cyberland.cpp:46:27: warning: narrowing conversion of 'to' from 'std::tuple_element<0, std::pair<int, int> >::type' {aka 'int'} to 'double' [-Wnarrowing]
   46 |     pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2)), nol});
      |                           ^~
cyberland.cpp:46:35: warning: narrowing conversion of '(dis + ((int)((dis < k) && (a.std::vector<int>::operator[](((std::vector<int>::size_type)to)) == 2))))' from 'int' to 'double' [-Wnarrowing]
   46 |     pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2)), nol});
      |                               ~~~~^~~~~~~~~~~~~~~~~~~~~
cyberland.cpp:46:58: warning: narrowing conversion of 'nol' from 'int' to 'double' [-Wnarrowing]
   46 |     pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2)), nol});
      |                                                          ^~~
cyberland.cpp:50:27: warning: narrowing conversion of 'to' from 'std::tuple_element<0, std::pair<int, int> >::type' {aka 'int'} to 'double' [-Wnarrowing]
   50 |     pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2)), nol|(a[to]==0)});
      |                           ^~
cyberland.cpp:50:35: warning: narrowing conversion of '(dis + ((int)((dis < k) && (a.std::vector<int>::operator[](((std::vector<int>::size_type)to)) == 2))))' from 'int' to 'double' [-Wnarrowing]
   50 |     pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2)), nol|(a[to]==0)});
      |                               ~~~~^~~~~~~~~~~~~~~~~~~~~
cyberland.cpp:50:61: warning: narrowing conversion of '(nol | (a.std::vector<int>::operator[](((std::vector<int>::size_type)to)) == 0))' from 'int' to 'double' [-Wnarrowing]
   50 |     pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2)), nol|(a[to]==0)});
      |                                                          ~~~^~~~~~~~~~~
#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...