10337 2024. 03. 31 18:15:56 szil Vázsony vonatjegyet vásárol cpp17 Elfogadva 100/100 718ms 104340 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 7ms 13588 KiB
2 Elfogadva 118ms 31840 KiB
subtask2 20/20
3 Elfogadva 56ms 22592 KiB
4 Elfogadva 342ms 64728 KiB
5 Elfogadva 254ms 53740 KiB
6 Elfogadva 219ms 44452 KiB
7 Elfogadva 259ms 53016 KiB
8 Elfogadva 211ms 43388 KiB
9 Elfogadva 477ms 78504 KiB
subtask3 15/15
10 Elfogadva 143ms 48168 KiB
11 Elfogadva 14ms 16628 KiB
12 Elfogadva 14ms 16852 KiB
13 Elfogadva 37ms 22696 KiB
14 Elfogadva 71ms 34992 KiB
subtask4 20/20
15 Elfogadva 61ms 27064 KiB
16 Elfogadva 194ms 38408 KiB
17 Elfogadva 41ms 24768 KiB
18 Elfogadva 71ms 30992 KiB
19 Elfogadva 41ms 22184 KiB
20 Elfogadva 76ms 27252 KiB
subtask5 45/45
21 Elfogadva 7ms 15808 KiB
22 Elfogadva 718ms 104340 KiB
23 Elfogadva 46ms 23916 KiB
24 Elfogadva 188ms 45692 KiB
25 Elfogadva 165ms 40424 KiB
26 Elfogadva 298ms 53644 KiB
27 Elfogadva 175ms 41092 KiB
28 Elfogadva 472ms 85604 KiB
29 Elfogadva 111ms 33440 KiB
30 Elfogadva 418ms 73460 KiB
31 Elfogadva 190ms 38584 KiB
32 Elfogadva 46ms 25992 KiB
33 Elfogadva 273ms 50892 KiB
34 Elfogadva 256ms 52252 KiB
35 Elfogadva 259ms 49124 KiB
36 Elfogadva 236ms 46180 KiB
37 Elfogadva 252ms 46224 KiB