| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1023221 | nam6 | 사이버랜드 (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
const long long INFINI = 1e17;
const int MAXI_K = 70;
vector<int> pouvoirs;
vector<int> dejaVu;
set<int> zeroAccess;
int fin;
struct Arc{
int dest;
int poids;
};
vector<vector<Arc>> adj;
struct Sit{
int node;
int nbDiv;
double dis;
bool operator <(const Sit &other) const{
return dis > other.dis;
}
};
void dfs(int n){
if(dejaVu[n] == 1) return;
dejaVu[n] = 1;
if(n == fin) return;
if(pouvoirs[n] == 0) zeroAccess.insert(n);
for(Arc arc : adj[n])
dfs(arc.dest);
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
pouvoirs = arr;
fin = H;;
K = min(K, MAXI_K);
dejaVu = vector<int>(N, 0);
adj = vector<vector<Arc>>(N);
for(int n=0; n<N; n++){
adj[x[n]].push_back({y[n], c[n]});
adj[y[n]].push_back({x[n], c[n]});
}
zeroAccess.clear();
zeroAccess.insert(0);
dfs(0);
if(!dejaVu[fin]) return -1;
vector<vector<int>> deja(N, vector<int>(K+1));
vector<vector<double>> distances(N, vector<double>(K+1, 1e17));
distances[fin][0]=0;
priority_queue<Sit> aTraiter;
aTraiter.push({fin, 0, 0});
while(!aTraiter.empty()){
Sit curSit = aTraiter.top();
aTraiter.pop();
if(curSit.node == fin && curSit.nbDiv != 0) continue;
if(deja[curSit.node][curSit.nbDiv]) continue;
if(zeroAccess.count(curSit.node)) return curSit.dis;
deja[curSit.node][curSit.nbDiv] = 1;
for(Arc voisin : adj[curSit.node]){
int v = voisin.dest;
int w = voisin.poids;
if( distances[curSit.node][curSit.nbDiv] + (double)w/(double)pow(2, curSit.nbDiv) < distances[v][curSit.nbDiv]){
distances[v][curSit.nbDiv] = distances[curSit.node][curSit.nbDiv] + (double)w/(double)pow(2, curSit.nbDiv);
aTraiter.push({v, curSit.nbDiv, distances[v][curSit.nbDiv]});
}
if(pouvoirs[v] == 2 && curSit.nbDiv < K){
if(distances[curSit.node][curSit.nbDiv] + (double)w/(double)pow(2, curSit.nbDiv) < distances[v][curSit.nbDiv + 1]){
distances[v][curSit.nbDiv + 1] = distances[curSit.node][curSit.nbDiv] + (double)w/(double)pow(2, curSit.nbDiv);
aTraiter.push({v, curSit.nbDiv+1, distances[v][curSit.nbDiv + 1]});
}
}
}
}
return -1;
}
int main() {
int T;
assert(1 == scanf("%d", &T));
while (T--){
int N,M,K,H;
assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
std::vector<int> x(M);
std::vector<int> y(M);
std::vector<int> c(M);
std::vector<int> arr(N);
for (int i=0;i<N;i++)
assert(1 == scanf("%d", &arr[i]));
for (int i=0;i<M;i++)
assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
}
}