103372024-03-31 18:15:56szilVázsony vonatjegyet vásárolcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva7ms13588 KiB
2Elfogadva118ms31840 KiB
subtask220/20
3Elfogadva56ms22592 KiB
4Elfogadva342ms64728 KiB
5Elfogadva254ms53740 KiB
6Elfogadva219ms44452 KiB
7Elfogadva259ms53016 KiB
8Elfogadva211ms43388 KiB
9Elfogadva477ms78504 KiB
subtask315/15
10Elfogadva143ms48168 KiB
11Elfogadva14ms16628 KiB
12Elfogadva14ms16852 KiB
13Elfogadva37ms22696 KiB
14Elfogadva71ms34992 KiB
subtask420/20
15Elfogadva61ms27064 KiB
16Elfogadva194ms38408 KiB
17Elfogadva41ms24768 KiB
18Elfogadva71ms30992 KiB
19Elfogadva41ms22184 KiB
20Elfogadva76ms27252 KiB
subtask545/45
21Elfogadva7ms15808 KiB
22Elfogadva718ms104340 KiB
23Elfogadva46ms23916 KiB
24Elfogadva188ms45692 KiB
25Elfogadva165ms40424 KiB
26Elfogadva298ms53644 KiB
27Elfogadva175ms41092 KiB
28Elfogadva472ms85604 KiB
29Elfogadva111ms33440 KiB
30Elfogadva418ms73460 KiB
31Elfogadva190ms38584 KiB
32Elfogadva46ms25992 KiB
33Elfogadva273ms50892 KiB
34Elfogadva256ms52252 KiB
35Elfogadva259ms49124 KiB
36Elfogadva236ms46180 KiB
37Elfogadva252ms46224 KiB