103372024-03-31 18:15:56szilVázsony vonatjegyet vásárolcpp17Accepted 100/100718ms104340 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100'001;

vector<pair<int, ll>> g[MAXN];
vector<int> g2[MAXN];
int dp[MAXN], siz[MAXN], comp[MAXN], nxt[MAXN], n, m, a, b;
ll dist[MAXN];

void dijkstra(int source) {
	fill(dist, dist+MAXN, 1e18);
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	dist[source] = 0;
	pq.push({0, source});
	while (!pq.empty()) {
		auto [d, u] = pq.top(); pq.pop();
		if (dist[u] < d) continue;
		for (auto [v, w] : g[u]) {
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				pq.push({dist[v], v});
			}
		}
	}
}

void dfs(int u, int c) {
	comp[u] = c;
	siz[c]++;
	for (auto [v, w] : g[u]) {
		if (!comp[v] && dist[u] == dist[v]) dfs(v, c);
	}
}

int timer = 1;
void build_graph() {
	for (int i = 1; i <= n; i++) {
		if (!comp[i]) dfs(i, timer++);
	}
	for (int i = 1; i <= n; i++) {
		for (auto [u, w] : g[i]) {
			if (dist[i] > dist[u]) g2[comp[i]].emplace_back(comp[u]);
		}
	}
	for (int i = 1; i < timer; i++) {
		sort(g2[i].begin(), g2[i].end());
		g2[i].erase(unique(g2[i].begin(), g2[i].end()), g2[i].end());
	}
}

int longest_route(int u) {
	if (dp[u] == -1) {
		dp[u] = INT_MIN;
		for (int v : g2[u]) {
			int x = longest_route(v) + siz[u];
			if (dp[u] < x) {
				nxt[u] = v;
				dp[u] = x;
			}
		}
	}
	return dp[u];
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	fill(dp, dp+MAXN, -1);
	cin >> n >> m >> a >> b;
	for (int i = 0; i < m; i++) {
		int u, v; ll w; cin >> u >> v >> w;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}
	dijkstra(b);
	build_graph();
	dp[comp[b]] = 0;
	longest_route(comp[a]);
	int u = comp[a];
	vector<int> good = {comp[b]};
	while (u != comp[b]) {
		good.emplace_back(u);
		u = nxt[u];
	}
	sort(good.begin(), good.end());
	vector<int> ans;
	for (int i = 1; i <= n; i++) {
		if (binary_search(good.begin(), good.end(), comp[i])) ans.emplace_back(i);
	}
	cout << ans.size() << "\n";
	for (int u : ans) cout << u << " ";
	cout << "\n";
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted7ms13588 KiB
2Accepted118ms31840 KiB
subtask220/20
3Accepted56ms22592 KiB
4Accepted342ms64728 KiB
5Accepted254ms53740 KiB
6Accepted219ms44452 KiB
7Accepted259ms53016 KiB
8Accepted211ms43388 KiB
9Accepted477ms78504 KiB
subtask315/15
10Accepted143ms48168 KiB
11Accepted14ms16628 KiB
12Accepted14ms16852 KiB
13Accepted37ms22696 KiB
14Accepted71ms34992 KiB
subtask420/20
15Accepted61ms27064 KiB
16Accepted194ms38408 KiB
17Accepted41ms24768 KiB
18Accepted71ms30992 KiB
19Accepted41ms22184 KiB
20Accepted76ms27252 KiB
subtask545/45
21Accepted7ms15808 KiB
22Accepted718ms104340 KiB
23Accepted46ms23916 KiB
24Accepted188ms45692 KiB
25Accepted165ms40424 KiB
26Accepted298ms53644 KiB
27Accepted175ms41092 KiB
28Accepted472ms85604 KiB
29Accepted111ms33440 KiB
30Accepted418ms73460 KiB
31Accepted190ms38584 KiB
32Accepted46ms25992 KiB
33Accepted273ms50892 KiB
34Accepted256ms52252 KiB
35Accepted259ms49124 KiB
36Accepted236ms46180 KiB
37Accepted252ms46224 KiB