103342024-03-31 17:37:08szilVázsony vonatjegyet vásárolcpp17Runtime error 0/100898ms263140 KiB
#include <algorithm>
#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], 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;
	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]) {
			if (dp[u] < longest_route(v) + 1) {
				nxt[u] = v;
				dp[u] = dp[v] + 1;
			}
		}
	}
	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;
	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
1Runtime error229ms263140 KiB
2Runtime error379ms262900 KiB
subtask20/20
3Runtime error272ms262664 KiB
4Runtime error601ms262428 KiB
5Runtime error523ms262196 KiB
6Runtime error481ms261968 KiB
7Runtime error460ms261968 KiB
8Runtime error481ms261756 KiB
9Runtime error657ms261524 KiB
subtask30/15
10Runtime error354ms261292 KiB
11Runtime error286ms261300 KiB
12Runtime error284ms261280 KiB
13Runtime error254ms261052 KiB
14Runtime error282ms260820 KiB
subtask40/20
15Runtime error263ms260604 KiB
16Runtime error437ms260600 KiB
17Runtime error248ms260380 KiB
18Runtime error326ms260380 KiB
19Runtime error254ms260372 KiB
20Runtime error282ms260360 KiB
subtask50/45
21Runtime error224ms260380 KiB
22Runtime error898ms260392 KiB
23Runtime error264ms260164 KiB
24Runtime error395ms260168 KiB
25Runtime error370ms260164 KiB
26Runtime error541ms260152 KiB
27Runtime error374ms260152 KiB
28Runtime error735ms259940 KiB
29Runtime error375ms259936 KiB
30Runtime error686ms259940 KiB
31Runtime error453ms259788 KiB
32Runtime error263ms259812 KiB
33Runtime error465ms259796 KiB
34Runtime error499ms259804 KiB
35Runtime error504ms259808 KiB
36Runtime error500ms259792 KiB
37Runtime error437ms259804 KiB