103362024-03-31 18:13:48szilVázsony vonatjegyet vásárolcpp17Wrong answer 55/100639ms104340 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]) {
			if (dp[u] < longest_route(v) + 1) {
				nxt[u] = v;
				dp[u] = dp[v] + 1;
			}
		}
		if (dp[u] != INT_MIN) dp[u] += siz[u];
	}
	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
1Accepted8ms13592 KiB
2Accepted120ms31836 KiB
subtask220/20
3Accepted59ms22624 KiB
4Accepted347ms64784 KiB
5Accepted261ms53924 KiB
6Accepted284ms44820 KiB
7Accepted287ms53148 KiB
8Accepted231ms44156 KiB
9Accepted490ms79172 KiB
subtask315/15
10Accepted150ms49148 KiB
11Accepted14ms17552 KiB
12Accepted16ms17656 KiB
13Accepted37ms23728 KiB
14Accepted71ms36260 KiB
subtask420/20
15Accepted61ms28132 KiB
16Accepted184ms39200 KiB
17Accepted41ms25580 KiB
18Accepted79ms31792 KiB
19Accepted39ms22732 KiB
20Accepted78ms27532 KiB
subtask50/45
21Accepted8ms16008 KiB
22Wrong answer639ms104340 KiB
23Wrong answer50ms24252 KiB
24Accepted194ms45908 KiB
25Wrong answer178ms40724 KiB
26Accepted305ms53812 KiB
27Accepted171ms41632 KiB
28Wrong answer529ms86404 KiB
29Accepted118ms34064 KiB
30Wrong answer460ms74336 KiB
31Accepted199ms39588 KiB
32Accepted50ms26588 KiB
33Accepted305ms51496 KiB
34Accepted247ms52892 KiB
35Accepted270ms49644 KiB
36Accepted261ms46616 KiB
37Accepted266ms46452 KiB