求 Hack

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef double lf;
static constexpr int N = 5e5 + 50, inf = 0x3f3f3f3f3f3f3f3fll, W = -800;
int cnt = 0,p[N];
namespace _g {
	int head[N], nxt[N << 1], to[N << 1], weight[N << 1], tot, d[N];
	int dis[N], cnt[N], n;
	bitset<N> vis;
	inline void add(const int& u, const int& v, const int& w = 1) {
		to[++tot] = v;
		weight[tot] = w;
		nxt[tot] = head[u];
		head[u] = tot;
	}
	inline void spfa(int s) {
		memset(dis, 0x3f, sizeof dis);
		memset(cnt, 0, sizeof cnt);
		vis.reset();
		dis[s] = 0;
		cnt[s] = 1;
		queue<int> q;
		q.push(s);
		vis[s] = 1;
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			vis[u] = 0;
			for (int i = head[u]; i; i = nxt[i]) {
				int v = to[i], w = weight[i];
				if (dis[v] > dis[u] + w) {
					dis[v] = dis[u] + w;
					++cnt[v];
					if (!vis[v]) q.push(v), vis[v] = 1;
					if (dis[q.back()] < dis[q.front()]) swap(q.front(), q.back());
				}
			}
		}
	}
}
struct _Queue{
    int q[N],hh,tt;
    int &front(){
        return q[hh];
    }
    int &back(){
        return q[tt];
    }
    void pop_front(){
        hh=p[hh];
    }
    void push_back(int x){
        q[tt=p[tt]]=x;
    }
    bool empty(){
        return p[tt]==hh;
    }
    void clear(){
        hh=1;
        tt=0;
    }
}q;
namespace G {
	int head[N], nxt[N << 1], to[N << 1], weight[N << 1], tot;
	int dis[N], f[N], n, e;
	bitset<N> vis;
	inline void add(const int& u, const int& v, const int& w = 1) {
		to[++tot] = v;
		weight[tot] = w;
		nxt[tot] = head[u];
		head[u] = tot;
	}
	inline void spfa_star(lf a, lf b,int limit) {
        q.clear();
		vis.reset();
		for (int i = 1; i <= n; ++i) {
			if (dis[i] <= 1e9) {
				vis[i] = 1;
				q.push_back(i);
			}
		}
		while (!q.empty()) {
			int u = q.front();
			q.pop_front();
			vis[u] = 0;
			for (int i = head[u]; i; i = nxt[i]) {
				int v = to[i], w = weight[i], t = dis[v];
				if (t > dis[u] + w && w<=limit) {
					f[v] = (dis[v] = dis[u] + w) + b * _g::dis[v];
					if (!vis[v] && t > a * dis[v]) q.push_back(v), vis[v] = 1;
					if (f[q.back()] + W < f[q.front()]) swap(q.front(), q.back());
				}
			}
		}
	}
	void init(int s) {
		memset(dis, 0x3f, sizeof dis);
		dis[s] = 0;
		f[s] = _g::dis[s];
	}
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m, s, t = 0;
	cin >> n >> m >> s;
	G::n = _g::n = n;
    for(int i=0;i<N-1;++i){
        p[i]=i+1;
    }
    p[N-1]=0;
	for (int i = 1, u, v, w; i <= m; ++i) {
		cin >> u >> v >> w;
		G::add(u, v, w);
		_g::add(v, u, w);
		++_g::d[v];
		if (_g::d[v] > _g::d[t]) t = v;
		if (w == 1)++cnt;
	}
	_g::spfa(t);
	G::init(s);
	G::spfa_star(10, 0.8,2);
	G::spfa_star(7.2, 0.8,5);
	G::spfa_star(5.4, 0.8,10);
	G::spfa_star(3.2, 0.8,100);
	G::spfa_star(2.4, 0.8,500);
	G::spfa_star(2.0, 0.8,1200);
	G::spfa_star(1.6, 0.8,2000);
	G::spfa_star(1, 0.8,1e9);
	for (int i = 1; i <= n; ++i) {
		cout << G::dis[i] << ' ';
	}
	return 0;
}