91712024-02-16 19:22:57UVinceA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 32/40143ms44508 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,m,start,end;
	cin>>n>>m>>start>>end;
	vector<vector<pair<int,int>>> adj(n+m);
	for (int i=0;i<n;i++){
		int ai;
		cin>>ai;
		for (int j=0; j<ai; j++) {
			int a;
			cin>>a;
			adj[a].push_back({m+i,1});
			adj[m+i].push_back({a,0});
		}
	}
	deque<int> dq;
	vector<int> dist(n+m, INT_MAX);
	vector<int> parent(n+m);
	dq.push_back(start);
	dist[start]=0;
	parent[start]=-1;

	while (!dq.empty()){
		int v = dq.front();
		dq.pop_front();

		for (auto [to,dst] : adj[v]){
			if (dist[to]==INT_MAX){
				dist[to]=dist[v]+dst;
				parent[to]=v;
				if (dst){
					dq.push_back(to);
				}
				else {
					dq.push_front(to);
				}
			}
		}
	}
	if (dist[end]==INT_MAX){
		cout<<"-1";
		return 0;
	}

	cout<<dist[end]<<"\n";
	vector<int> ans;
	while (end!=-1){
		if (end>=m){
			ans.push_back(end-m);
		}
		end=parent[end];
	}
	reverse(ans.begin(),ans.end());
	for (int i : ans) cout<<i+1<<" ";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base32/40
1Elfogadva0/03ms1832 KiB
2Elfogadva0/04ms3484 KiB
3Elfogadva2/23ms2376 KiB
4Hibás válasz0/23ms2460 KiB
5Elfogadva2/23ms2884 KiB
6Hibás válasz0/22ms2756 KiB
7Elfogadva2/23ms3080 KiB
8Hibás válasz0/23ms3264 KiB
9Elfogadva2/24ms3728 KiB
10Elfogadva2/24ms3824 KiB
11Elfogadva2/23ms3284 KiB
12Hibás válasz0/26ms4336 KiB
13Elfogadva2/24ms4336 KiB
14Elfogadva2/24ms4348 KiB
15Elfogadva2/2143ms44048 KiB
16Elfogadva2/2143ms43804 KiB
17Elfogadva2/2143ms43752 KiB
18Elfogadva2/2143ms44508 KiB
19Elfogadva2/24ms4572 KiB
20Elfogadva2/24ms4860 KiB
21Elfogadva2/24ms4156 KiB
22Elfogadva2/24ms4916 KiB