103342024-03-31 17:37:08szilVázsony vonatjegyet vásárolcpp17Futási hiba 0/100898ms263140 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;
	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
1Futási hiba229ms263140 KiB
2Futási hiba379ms262900 KiB
subtask20/20
3Futási hiba272ms262664 KiB
4Futási hiba601ms262428 KiB
5Futási hiba523ms262196 KiB
6Futási hiba481ms261968 KiB
7Futási hiba460ms261968 KiB
8Futási hiba481ms261756 KiB
9Futási hiba657ms261524 KiB
subtask30/15
10Futási hiba354ms261292 KiB
11Futási hiba286ms261300 KiB
12Futási hiba284ms261280 KiB
13Futási hiba254ms261052 KiB
14Futási hiba282ms260820 KiB
subtask40/20
15Futási hiba263ms260604 KiB
16Futási hiba437ms260600 KiB
17Futási hiba248ms260380 KiB
18Futási hiba326ms260380 KiB
19Futási hiba254ms260372 KiB
20Futási hiba282ms260360 KiB
subtask50/45
21Futási hiba224ms260380 KiB
22Futási hiba898ms260392 KiB
23Futási hiba264ms260164 KiB
24Futási hiba395ms260168 KiB
25Futási hiba370ms260164 KiB
26Futási hiba541ms260152 KiB
27Futási hiba374ms260152 KiB
28Futási hiba735ms259940 KiB
29Futási hiba375ms259936 KiB
30Futási hiba686ms259940 KiB
31Futási hiba453ms259788 KiB
32Futási hiba263ms259812 KiB
33Futási hiba465ms259796 KiB
34Futási hiba499ms259804 KiB
35Futási hiba504ms259808 KiB
36Futási hiba500ms259792 KiB
37Futási hiba437ms259804 KiB