91712024-02-16 19:22:57UVinceA lehető legkevesebb metróval utazás (40 pont)cpp17Wrong answer 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<<" ";
}
SubtaskSumTestVerdictTimeMemory
base32/40
1Accepted0/03ms1832 KiB
2Accepted0/04ms3484 KiB
3Accepted2/23ms2376 KiB
4Wrong answer0/23ms2460 KiB
5Accepted2/23ms2884 KiB
6Wrong answer0/22ms2756 KiB
7Accepted2/23ms3080 KiB
8Wrong answer0/23ms3264 KiB
9Accepted2/24ms3728 KiB
10Accepted2/24ms3824 KiB
11Accepted2/23ms3284 KiB
12Wrong answer0/26ms4336 KiB
13Accepted2/24ms4336 KiB
14Accepted2/24ms4348 KiB
15Accepted2/2143ms44048 KiB
16Accepted2/2143ms43804 KiB
17Accepted2/2143ms43752 KiB
18Accepted2/2143ms44508 KiB
19Accepted2/24ms4572 KiB
20Accepted2/24ms4860 KiB
21Accepted2/24ms4156 KiB
22Accepted2/24ms4916 KiB