TLE on #6

Code

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

constexpr const int N = 1e5 + 3;
vector<pair<int, int>> G[N];
bitset<N> ins;
int n;
LL dis[N];

void SPFA(int rt) {
	for(int i = 1; i <= n; ++i)
		dis[i] = 0x3f3f3f3f;
	dis[rt] = 0;
	deque<int> q;
	q.push_back(rt);
	ins.reset();
	ins[rt] = true;
	LL tot = dis[rt];
	int cnt = 1;
	while(!q.empty()) {
		int u = q.front();
//		while(dis[u] * cnt > tot) { // LLL
//			q.pop_front(); // 开启后反而多了 TLE on #1
//			q.push_back(u);
//			u = q.front();
//		}
		q.pop_front();
		ins[u] = false;
		if(!q.empty() && dis[q.back()] < dis[q.front()]) // SLF
			swap(q.front(), q.back());
		tot -= dis[u];
		--cnt;
		for(const auto& [v, w]: G[u])
			if(dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if(!ins[v]) {
					q.push_back(v);
					ins[v] = true;
					if(dis[q.back()] < dis[q.front()]) // SLF
						swap(q.front(), q.back());
					tot += dis[v];
					++cnt;
				}
			}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int m, st;
	cin >> n >> m >> st;
	for(int u, v, w; m--; ) {
		cin >> u >> v >> w;
		G[u].push_back({v, w});
	}
	SPFA(st);
	for(int i = 1; i <= n; ++i)
		cout << dis[i] << ' ';
	cout << endl;
	return 0;
}