103362024-03-31 18:13:48szilVázsony vonatjegyet vásárolcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva8ms13592 KiB
2Elfogadva120ms31836 KiB
subtask220/20
3Elfogadva59ms22624 KiB
4Elfogadva347ms64784 KiB
5Elfogadva261ms53924 KiB
6Elfogadva284ms44820 KiB
7Elfogadva287ms53148 KiB
8Elfogadva231ms44156 KiB
9Elfogadva490ms79172 KiB
subtask315/15
10Elfogadva150ms49148 KiB
11Elfogadva14ms17552 KiB
12Elfogadva16ms17656 KiB
13Elfogadva37ms23728 KiB
14Elfogadva71ms36260 KiB
subtask420/20
15Elfogadva61ms28132 KiB
16Elfogadva184ms39200 KiB
17Elfogadva41ms25580 KiB
18Elfogadva79ms31792 KiB
19Elfogadva39ms22732 KiB
20Elfogadva78ms27532 KiB
subtask50/45
21Elfogadva8ms16008 KiB
22Hibás válasz639ms104340 KiB
23Hibás válasz50ms24252 KiB
24Elfogadva194ms45908 KiB
25Hibás válasz178ms40724 KiB
26Elfogadva305ms53812 KiB
27Elfogadva171ms41632 KiB
28Hibás válasz529ms86404 KiB
29Elfogadva118ms34064 KiB
30Hibás válasz460ms74336 KiB
31Elfogadva199ms39588 KiB
32Elfogadva50ms26588 KiB
33Elfogadva305ms51496 KiB
34Elfogadva247ms52892 KiB
35Elfogadva270ms49644 KiB
36Elfogadva261ms46616 KiB
37Elfogadva266ms46452 KiB