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

#include<bits/stdc++.h>
#define pii pair<double,int>
#define pb push_back
#define fi first
#define se second
#define ls now<<1
#define rs now<<1|1
#define QwQ puts("QwQ")
using namespace std;
const int N=10000005;
int n,m,k,h,vis[N];
double dis[N];
struct node
{
	int to,w,tp;
};
vector<node>e[N];
priority_queue<pii>q;
inline int read()
{
	int ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		ans=(ans<<3)+(ans<<1)+(c^48);
		c=getchar();
	}
	return ans*f;
}
inline void write(int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
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)
{
	n=N,m=M,k=K,h=H;
	k=min(k,72);
	for(int i=0;i<n;i++) e[i].clear();
	for(int i=0;i<m;i++)
	{
		e[x[i]].pb({y[i],c[i],2});
		e[y[i]].pb({x[i],c[i],2});
		for(int j=1;j<=k;j++)
		{
			if(x[i]!=h&&arr[y[i]]==2) e[x[i]+(j-1)*n].pb({y[i]+j*n,c[i],1});
			if(y[i]!=h&&arr[x[i]]==2) e[y[i]+(j-1)*n].pb({x[i]+j*n,c[i],1});
			if(x[i]!=h) e[x[i]+j*n].pb({y[i]+j*n,c[i],2});
			if(y[i]!=h) e[y[i]+j*n].pb({x[i]+j*n,c[i],2});
		}
	}
	for(int i=1;i<=k;i++)
	{
		e[h+(i-1)*n].pb({h+i*n,0,2});
	}
	for(int i=0;i<=(k+1)*n;i++)
	{
		dis[i]=1e24;
		vis[i]=0;
	}
	for(int i=0;i<n;i++)
	{
		if((!i)||(!arr[i]))
		{
			dis[i]=0;
			q.push({0,i});
		}
	}
	while(!q.empty())
	{
		pii u=q.top();
		q.pop();
		if(vis[u.se]) continue;
		vis[u.se]=1;
		for(auto v:e[u.se])
		{
			if(v.tp==1)
			{
				if(dis[v.to]>(dis[u.se]+v.w)/2.0)
				{
					dis[v.to]=(dis[u.se]+v.w)/2.0;
					q.push({-dis[v.to],v.to});
				}
			}
			if(v.tp==2)
			{
				if(dis[v.to]>dis[u.se]+v.w)
				{
					dis[v.to]=dis[u.se]+v.w;
					q.push({-dis[v.to],v.to});
				}
			}
		}
	}
	if(dis[h+k*n]>=1e24) return -1;
	return dis[h+k*n];
}