提交记录

调了好久了。

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
typedef long double ld;

const int n = 7e6 + 10;
ld dis[n], ans = 1e18;
vector<double> z;
bool vis[n];

struct pii{
	int v; ld w;
	
	bool operator < (const pii & o) const{
		return w > o.w;
	}
};
vector<pii> g[n];
priority_queue<pii> pq;

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	ans = 1e18;
	for(int i = 0; i < M; i++){
		z.push_back(c[i]);
	}
	K = min(K, 70);
	for(int i = 0; i < K; i++){
		for(int j = 0; j < M; j++){
			g[x[j]+i*N].push_back({y[j]+i*N, z[j]});
			g[y[j]+i*N].push_back({x[j]+i*N, z[j]});
			z[j] /= 2;
		}
		if(i < K-1){
			for(int j = 0; j < N; j++){
				if(arr[j] == 2) g[j+i*N].push_back({j+(i+1)*N, 0});
			}
		}
	}
	pq.push({H, 0});
	for(int i = 0; i < K*N; i++) dis[i] = 1e18;
	dis[H] = 0;
	while(pq.size()){
		int u = pq.top().v;
		pq.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(pii ed: g[u]){
			if(dis[ed.v] > dis[u] + ed.w){
				dis[ed.v] = dis[u] + ed.w;
				pq.push({ed.v, dis[ed.v]});
			}
		}
	}
	for(int i = 0; i < K*N; i += N) ans = min(ans, dis[i]);
	for(int i = 0; i < N; i++){
		if(arr[i] == 0){
			for(int j = i; j < K*N; j += N) ans = min(ans, dis[j]);
		}
	}
	for(int i = 0; i < K*N; i++) g[i].clear();
	while(pq.size()) pq.pop();
	for(int i = 0; i < K*N; i++) dis[i] = vis[i] = 0;
	z.clear(); x.clear(); y.clear(); c.clear(); arr.clear();
    return ans;
}