| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 981977 | vjudge1 | 앨리스, 밥, 서킷 (APIO23_abc) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a:b)
#define pll pair<ll, ll>
#define fi first
#define se second
#define state array<double, 3>
#define pb push_back
#define ll long long
using namespace std;
const double inf=1e18;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
if(K>30) return -1;
vector<pll> adj[N];
rep(i,0,M){
adj[x[i]].pb({y[i],c[i]});
adj[y[i]].pb({x[i],c[i]});
}
double dis[N][35]{};
rep(i,0,N) rep(j,0,K+1) dis[i][j]=inf;
priority_queue<state, vector<state>, greater<state>> pq;
pq.push({0,0,0});
dis[0][0]=0;
while(pq.size()){
int u=pq.top()[1], k=pq.top()[2];
double w=pq.top()[0];
pq.pop();
if(dis[u][k]<w || u==H) continue;
cout<<u<<" "<<k<<" "<<w<<endl;
if(arr[u]==2){
repa(v,adj[u]){
if(k<K && dis[u][k+1]>(dis[u][k]+v.se+v.se)/2){
dis[u][k+1]=(dis[u][k]+v.se+v.se)/2;
pq.push({dis[u][k+1],u,k+1});
}
}
}
repa(v,adj[u]){
if(dis[v.fi][k]>dis[u][k]+v.se){
dis[v.fi][k]=dis[u][k]+v.se;
pq.push({dis[v.fi][k],v.fi,k});
}
if(k<K && arr[v.fi]==2 && dis[v.fi][k+1]>(dis[u][k]+v.se)/2){
dis[v.fi][k+1]=(dis[u][k]+v.se)/2;
pq.push({dis[v.fi][k+1],v.fi,k+1});
}
if(!arr[v.fi] && dis[v.fi][k]){
dis[v.fi][k]=0;
pq.push({dis[v.fi][k],v.fi,k});
}
}
}
double ans=inf;
rep(i,0,K) ans=min(ans,dis[H][i]);
/*rep(i,0,N){
cout<<i<<": ";
rep(j,0,K) cout<<dis[i][j]<<" ";
cout<<endl;
}*/
if(ans==inf) return -1;
else return ans;
}