| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 773291 | AmirElarbi | 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 ve vector
#define vi vector<int>
#define vii vector<ii>
#define ii pair<int,int>
#define fi first
#define se second
#define ll long long
#define INF 1e18+7
#define pb push_back
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
const int MOD = 1e9+7;
const int nax = 2e5+5;
const int kax = 60+5;
void readio(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
//#include "cyberland.h"
vii adj[nax];
bool vis[nax];
double dist[nax][kax];
void dfs(int u, int nt){
if(vis[u]) return;
vis[u] = 1;
for(auto x : adj[u]){
if(x.fi == nt) continue;
dfs(x.fi, nt);
}
}
double solve(int n, int m, int k, int h, vi x, vi y, vi c, vi arr) {
for (int i = 0; i < n; ++i)
{
adj[i].clear();
vis[i] = 0;
for (int j = 0; j <= min(k,kax); ++j)
{
dist[i][j] = INF;
}
}
for (int i = 0; i < m; ++i)
{
adj[x[i]].pb({y[i], c[i]});
adj[y[i]].pb({x[i], c[i]});
}
dfs(0,h);
priority_queue<pair<pair<double,int>,int>, ve<pair<pair<double,int>,int>>, greater<pair<pair<double,int>,int>>> pq;
for (int i = 0; i < n; ++i)
{
if((arr[i] == 0 && vis[i])|| !i){
dist[i][0] = 0;
pq.push({{0,0}, i});
}
}
while(!pq.empty()){
int u = pq.top().se, nb = pq.top().fi.se;
double cst = pq.top().fi.fi;
pq.pop();
if(dist[u][nb] != cst) continue;
if(u == h) continue;
for(auto x : adj[u]){
if(dist[u][nb]+x.se < dist[x.fi][nb]){
dist[x.fi][nb] = dist[u][nb]+x.se;
pq.push({{dist[x.fi][nb], nb}, x.fi});
}
if(nb < min(k,kax) && arr[x.fi] == 2 && (dist[u][nb]+x.se)*0.5 < dist[x.fi][nb+1]){
dist[x.fi][nb+1] = (dist[u][nb]+x.se)*0.5;
pq.push({{dist[x.fi][nb+1], nb+1}, x.fi});
}
}
}
double ans = INF;
for (int i = 0; i <= min(k,kax); ++i)
{
ans = min(ans, dist[h][i]);
}
if(ans == INF) return -1;
return ans;
}
int main() {
optimise;
readio();
int T;
int cnt = 0;
assert(1 == scanf("%d", &T));
while (T--){
cnt++;
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]));
if(cnt == 211) printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
}
}