| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 967073 | Batorgil952 | Cyberland (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
const int N=1e5+5;
vector< pair< int, int > > v[N];
double T[N][82];
bool B[N];
int DFS(int p, int g){
if(p==g) return 1;
int vn=v[p].size();
int s=0;
for(int i=0; i<vn; i++){
if(!B[v[p][i].ff]){
B[v[p][i].ff]=true;
s=max(s, DFS(v[p][i].ff, g));
}
}
return s;
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
priority_queue< pair< double, pair< ll, ll > >, vector< pair< double, pair< ll, ll > > >, greater< pair< double, pair< ll, ll > > > > q;
for(int i=0; i<N; i++){
v[i].clear();
for(int j=0; j<=69; j++){
T[i][j]=1000000000000000000.0;
}
B[i]=false;
}
for(int i=0; i<M; i++){
v[x[i]].pb(mp(y[i], c[i]));
v[y[i]].pb(mp(x[i], c[i]));
}
B[0]=true;
if(DFS(0, H)==0){
return -1;
}
if(K>=80){
for(int i=0; i<N; i++){
if(arr[i]==0) T[i][0]=0;
else if(arr[i]==2) T[i][0]=0;
else if(arr[i]==1) T[i][0]=1000000000000000000.0;
}
double ans=1000000000000000000.0;
q.push(mp(0, mp(H, 0)));
T[H][0]=0;
T[0][0]=0;
while(!q.empty()){
int x=q.top().ss.ff;
int z=q.top().ss.ss;
double y=q.top().ff;
q.pop();
if(y>T[x][z]){
continue;
}
int vn=v[x].size();
double ze=0.0;
for(int i=0; i<vn; i++){
if(!B[v[x][i].ff]){
continue;
}
if(arr[v[x][i].ff]==1){
if(T[v[x][i].ff][z]>T[x][z]+v[x][i].ss*1.0){
T[v[x][i].ff][z]=T[x][z]+v[x][i].ss*1.0;
q.push(mp(T[v[x][i].ff][z], mp(v[x][i].ff, z)));
}
}
if(arr[v[x][i].ff]==2 || arr[v[x][i].ff]==0){
ans=min(ans, T[x][0]+v[x][i].ss*1.0);
}
}
}
return ans;
}
q.push(mp(0, mp(0, 0)));
for(int i=0; i<=79; i++){
T[0][i]=0;
}
while(!q.empty()){
int x=q.top().ss.ff;
int z=q.top().ss.ss;
double y=q.top().ff;
q.pop();
if(x==H){
continue;
}
if(y>T[x][z] || z>K){
continue;
}
int vn=v[x].size();
double ze=0.0;
for(int i=0; i<vn; i++){
if(arr[v[x][i].ff]==1){
if(T[v[x][i].ff][z]>T[x][z]+v[x][i].ss*1.0){
T[v[x][i].ff][z]=T[x][z]+v[x][i].ss*1.0;
q.push(mp(T[v[x][i].ff][z], mp(v[x][i].ff, z)));
}
}
if(arr[v[x][i].ff]==2){
if(T[v[x][i].ff][z+1]>(T[x][z]+v[x][i].ss*1.0)/2.0){
T[v[x][i].ff][z+1]=(T[x][z]+v[x][i].ss*1.0)/2.0;
q.push(mp(T[v[x][i].ff][z+1], mp(v[x][i].ff, z+1)));
}
if(T[v[x][i].ff][z]>T[x][z]+v[x][i].ss*1.0){
T[v[x][i].ff][z]=T[x][z]+v[x][i].ss*1.0;
q.push(mp(T[v[x][i].ff][z], mp(v[x][i].ff, z)));
}
}
if(arr[v[x][i].ff]==0){
if(T[v[x][i].ff][z]>ze){
T[v[x][i].ff][z]=ze;
q.push(mp(T[v[x][i].ff][z], mp(v[x][i].ff, z)));
}
}
}
}
double ans=T[H][0];
for(int i=1; i<=K; i++){
ans=min(ans, T[H][i]);
}
return ans;
}
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));
}
}