| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 878663 | hello_there_123 | 사이버랜드 (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#include "cyberland.h"
double solve(int N, int M, int K, int end, std::vector<int> x, std::vector<int> y, std::vector<int> z, std::vector<int> arr) {
vector<pair<int,int> >v[N+3]; //node, val
for(int i=0;i<M;i++){
v[x[i]].push_back(make_pair(y[i],z[i]));
v[y[i]].push_back(make_pair(x[i],z[i]));
}
priority_queue<pair<double, pair<int,int> >, vector<pair<double,pair<int,int> > >, greater<pair<double,pair<int,int> > > > pq;
//val, node, k
double dist[N+3][K+3];
bool vis[N+3];f
memset(vis,0,sizeof(vis));
queue<int>q;
q.push(0);
vis[0] = 1;
while(!q.empty()){
int no = q.front();
q.pop();
for(auto p:v[no]){
if(!vis[p.first])q.push(p.first);
vis[p.first] = 1;
}
}
for(int i=0;i<N;i++){
if(vis[i] == 1 && (arr[i] == 0 || i==0)){
pq.push(mp(0,mp(i,0)));
for(int j=0;j<=K;j++) dist[i][j] = 0;
}
else for(int j=0;j<=K;j++) dist[i][j] = -1;
}
while(!pq.empty()){
double val = pq.top().first;
int no = pq.top().second.first;
int k = pq.top().second.second;
pq.pop();
if(no == end) continue;
for(auto p: v[no]){
if(dist[p.first][k] == -1 || dist[p.first][k] > val + (double) p.second){
dist[p.first][k] = val+(double)p.second;
pq.push(mp(val+(double)p.second,mp(p.first,k)));
}
if(k == K || arr[p.first]!=2) continue;
if(dist[p.first][k+1] == -1 || dist[p.first][k+1] > (val+(double)p.second)/2){
dist[p.first][k+1] = (val+(double)p.second)/2;
pq.push(mp((val+(double)p.second)/2, mp(p.first,k+1)));
}
}
}
double ans = 1e15;
for(int i=0;i<=K;i++){
if(dist[end][i]!=-1) ans = min(ans, dist[end][i]);
}
if(ans != 1e15) return ans;
else return -1;
}