在线求助代码复杂度

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define pll pair <ll, ll>
#define fi first
#define se second
#define y1 noip200

using namespace std;

const int N = 5e5 + 50, p = 1e9 + 7, inf = 1 << 29;

int n, m, s, t;
int dist[N];
set <pii> q;
vector <pii> e[N];

void init() {

}

void dijkstra(int S) {
	memset(dist, 127, sizeof(dist));
	dist[S] = 0;
	q.clear();
	for (int i = 1; i <= n; i++) q.insert({dist[i], i});
	while (!q.empty()) {
		int u = q.begin()->se;
		q.erase(q.begin());
		for (auto [v, w] : e[u]) 
			if (dist[v] > dist[u] + w) {
				q.erase({dist[v], v});
				dist[v] = dist[u] + w;
				q.insert({dist[v], v});
			}
	}
}

void solve() {
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		e[u].push_back({v, 0});
		e[v].push_back({u, 0});
	}
	for (int i = 0; i < e[s].size(); i++) 
		e[s][i].se = 1;
	for (int i = 0; i < e[t].size(); i++) 
		e[t][i].se = 0;
	dijkstra(t);
	int cnt1 = 0, cnt2 = 0;
	for (int i = 1; i <= n; i++) 
		if (dist[i]) 
			++cnt1;
	for (int i = 0; i < e[s].size(); i++) 
		e[s][i].se = 0;
	for (int i = 0; i < e[t].size(); i++) 
		e[t][i].se = 1;
	dijkstra(s);
	for (int i = 1; i <= n; i++) 
		if (dist[i]) 
			++cnt2;
	cout << 1LL * cnt1 * cnt2 << endl;
	for (int i = 1; i <= n; i++) e[i].clear();
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	init();
	int t = 1;
	cin >> t;
	while (t--) solve();
	return 0;
}