https://www.luogu.com.cn/record/111354243

#include <bits/stdc++.h>
//#include "cyberland.h" 
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define pdi pair<long double, int>
#define deb(var) cerr << "deb: " << #var << "=" << (var) << "; "
int n, m, k, t, sql[1000010];
vector<pii> g[1000010];
bool bk[1000010];
long double dis[1000010];
const long double eps = 0;
void dijk() {
	priority_queue<pdi, vector<pdi>, greater<pdi> > q;
	while (q.size()) q.pop();
	for (int i = 1; i <= n; i++) {
		bk[i] = 0, q.push(mp(dis[i], i)); dis[i] = 1e18;
	}
	while (q.size()) {
		int u = q.top().se; long double d = q.top().fi; q.pop();
		if (bk[u] || u == t) continue; bk[u] = 1;
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i].fi, w = g[u][i].se;
			if (dis[v] + eps >= d + w) {
				dis[v] = d + w; q.push(mp(dis[v], v));
			}
		}
	}
}
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) {
	K = min(K, 80);
	n = N, m = M, k = K, t = H + 1;
	for (int i = 1; i <= n; i++) sql[i] = arr[i - 1], g[i].clear();
	for (int i = 0; i < m; i++) g[x[i] + 1].pb(mp(y[i] + 1, c[i])), g[y[i] + 1].pb(mp(x[i] + 1, c[i]));
	fill(dis, dis + n + 1, 1e18);
	dis[1] = 0;
	for (int i = 2; i <= n; i++)
		if (sql[i] == 0) dis[i] = 0;
	dijk();
	long double ans = 1e18;
	ans = min(ans, dis[t]); dis[t] = 1e18;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= n; j++)
			if (sql[j] == 2) {
				if (dis[j] < 1e18 - eps) dis[j] /= 2;
			} else dis[j] = 1e18;
		dijk(); ans = min(ans, dis[t]); dis[t] = 1e18;
	}
	return ans >= 1e18 - eps ? -1 : (double)ans;
}
//vector<int> x, y, c, arr;
//signed main() {
//	int T;
//	cin >> T;
//	while (T--) {
//		int N, M, K, H;
//		cin >> N >> M >> K >> H;
//		x.clear(); y.clear(); c.clear(); arr.clear();
//		for (int i = 0; i < N; i++) {
//			int x; cin >> x; arr.pb(x);
//		}
//		for (int i = 0; i < M; i++) {
//			int u, v, w; cin >> u >> v >> w; x.pb(u), y.pb(v), c.pb(w);
//		}
//		cout << solve(N, M, K, H, x, y, c, arr) << "\n";
//	}
//	return 0; 
//}