103352024-03-31 17:41:53szilVázsony vonatjegyet vásárolcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva7ms13584 KiB
2Hibás válasz122ms31796 KiB
subtask220/20
3Elfogadva57ms22508 KiB
4Elfogadva345ms64200 KiB
5Elfogadva261ms53192 KiB
6Elfogadva229ms43904 KiB
7Elfogadva266ms52048 KiB
8Elfogadva233ms42972 KiB
9Elfogadva493ms77792 KiB
subtask315/15
10Elfogadva143ms48472 KiB
11Elfogadva14ms16684 KiB
12Elfogadva16ms17228 KiB
13Elfogadva37ms23264 KiB
14Elfogadva70ms35544 KiB
subtask40/20
15Hibás válasz59ms27172 KiB
16Hibás válasz179ms38188 KiB
17Elfogadva43ms24760 KiB
18Hibás válasz74ms31088 KiB
19Hibás válasz37ms22524 KiB
20Hibás válasz72ms27272 KiB
subtask50/45
21Hibás válasz7ms15892 KiB
22Hibás válasz718ms103884 KiB
23Hibás válasz48ms24248 KiB
24Hibás válasz194ms45928 KiB
25Hibás válasz179ms40612 KiB
26Hibás válasz282ms53576 KiB
27Elfogadva168ms41152 KiB
28Hibás válasz532ms85524 KiB
29Hibás válasz119ms33660 KiB
30Hibás válasz463ms73968 KiB
31Elfogadva215ms39128 KiB
32Hibás válasz48ms26240 KiB
33Hibás válasz307ms50944 KiB
34Elfogadva273ms52612 KiB
35Elfogadva270ms49108 KiB
36Hibás válasz261ms46156 KiB
37Hibás válasz243ms46220 KiB