#include "cyberland.h"
#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 1e5 + 7;
const int Mod = 1e9 +7;
const int szBL = 50;
const ll INF = 1e13;
const int BASE = 137;
struct toEdge {
int v;
ll w;
};
int n, m, K, H;
int a[N];
vector<toEdge> ke[N];
long double dp[N][25];
bool canGo[N];
void BFS () {
queue<int> Q;
Q.push(1);
canGo[1] = 1;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
iter (&id, ke[u]) {
if (canGo[id.v] == 0) {
canGo[id.v] = 1;
if (id.v != H)
Q.push(id.v);
}
}
}
}
long double algo () {
BFS();
if (canGo[H] == 0) {
return -1;
}
struct Data {
ll u, k;
long double val;
};
struct cmp {
bool operator () (Data A, Data B) { return A.val > B.val; }
};
priority_queue<Data, vector<Data>, cmp> pq;
rep (i, 1, n) rep (k, 0, min(K, 30)) dp[i][k] = INF;
rep (i, 1, n) if ((i == 1) || (a[i] == 0 && canGo[i])) {
pq.push({i, 0, 0});
dp[i][0] = 0;
}
while (!pq.empty()) {
Data cur = pq.top();
int u = cur.u, k = cur.k;
pq.pop();
iter (&id, ke[u]) {
int v = id.v;
ll w = id.w;
if (a[v] == 0) continue;
else {
if (dp[v][k] > dp[u][k] + w) {
dp[v][k] = dp[u][k] + w;
pq.push({v, k, dp[v][k]});
}
if (a[v] == 2 && k < 30 && dp[v][k + 1] > (dp[u][k] + w) / 2) {
dp[v][k + 1] = (dp[u][k] + w) / 2;
pq.push({v, k + 1, dp[v][k + 1]});
}
}
}
}
long double res = INF;
rep (i, 0, 30) {
res = min(res, dp[H][i]);
}
return res;
}
long double solve (int _n, int _m, vector<int> _U, vector<int> _V, vector<int> _W, vector<int> _A) {
//void solution() {
// cin >> n >> m >> K >> H;
// rep (i, 1, n) cin >> a[i];
// rep (i, 1, m) {
// int u, v, w;
// cin >> u >> v>> w;
// ++u, ++v;
// ke[u].push_back({v, w});
// ke[v].push_back({u, w});
// }
n = _n;
m = _m;
rep (i, 1, n) {
a[i] = _A[i - 1];
}
rep (i, 0, m - 1) {
int u = _U[i], v = _V[i], w = _W[i];
++u, ++v;
ke[u].push_back({v, w});
ke[v].push_back({u, w});
}
return algo();
}
//#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
//int main () {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//// file ("c");
// int num_Test = 1;
// cin >> num_Test;
// while (num_Test--)
// solution();
//}
/*
1
3 2 30
2
1 2 1
1 2 12
2 0 4
3 2
0 1 5
0 2 5
1
1 2
*/
Compilation message
/usr/bin/ld: /tmp/ccRfKLY9.o: in function `main':
grader.cpp:(.text.startup+0x696): undefined reference to `solve(int, int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
