103352024-03-31 17:41:53szilVázsony vonatjegyet vásárolcpp17Wrong answer 35/100718ms103884 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;
	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
1Accepted7ms13584 KiB
2Wrong answer122ms31796 KiB
subtask220/20
3Accepted57ms22508 KiB
4Accepted345ms64200 KiB
5Accepted261ms53192 KiB
6Accepted229ms43904 KiB
7Accepted266ms52048 KiB
8Accepted233ms42972 KiB
9Accepted493ms77792 KiB
subtask315/15
10Accepted143ms48472 KiB
11Accepted14ms16684 KiB
12Accepted16ms17228 KiB
13Accepted37ms23264 KiB
14Accepted70ms35544 KiB
subtask40/20
15Wrong answer59ms27172 KiB
16Wrong answer179ms38188 KiB
17Accepted43ms24760 KiB
18Wrong answer74ms31088 KiB
19Wrong answer37ms22524 KiB
20Wrong answer72ms27272 KiB
subtask50/45
21Wrong answer7ms15892 KiB
22Wrong answer718ms103884 KiB
23Wrong answer48ms24248 KiB
24Wrong answer194ms45928 KiB
25Wrong answer179ms40612 KiB
26Wrong answer282ms53576 KiB
27Accepted168ms41152 KiB
28Wrong answer532ms85524 KiB
29Wrong answer119ms33660 KiB
30Wrong answer463ms73968 KiB
31Accepted215ms39128 KiB
32Wrong answer48ms26240 KiB
33Wrong answer307ms50944 KiB
34Accepted273ms52612 KiB
35Accepted270ms49108 KiB
36Wrong answer261ms46156 KiB
37Wrong answer243ms46220 KiB