9172 | 2024. 02. 16 19:27:23 | UVince | A lehető legkevesebb metróval utazás (40 pont) | cpp17 | Elfogadva 40/40 | 157ms | 45124 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;
a--;
adj[a].push_back({m+i,1});
adj[m+i].push_back({a,0});
}
}
start--;
end--;
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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 40/40 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 4ms | 3484 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2228 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2444 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2868 KiB | |||
6 | Elfogadva | 2/2 | 2ms | 2740 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 3056 KiB | |||
8 | Elfogadva | 2/2 | 3ms | 3240 KiB | |||
9 | Elfogadva | 2/2 | 4ms | 3608 KiB | |||
10 | Elfogadva | 2/2 | 4ms | 3548 KiB | |||
11 | Elfogadva | 2/2 | 3ms | 3312 KiB | |||
12 | Elfogadva | 2/2 | 6ms | 4412 KiB | |||
13 | Elfogadva | 2/2 | 6ms | 4664 KiB | |||
14 | Elfogadva | 2/2 | 4ms | 4944 KiB | |||
15 | Elfogadva | 2/2 | 144ms | 44316 KiB | |||
16 | Elfogadva | 2/2 | 156ms | 44132 KiB | |||
17 | Elfogadva | 2/2 | 145ms | 44056 KiB | |||
18 | Elfogadva | 2/2 | 157ms | 45124 KiB | |||
19 | Elfogadva | 2/2 | 4ms | 4804 KiB | |||
20 | Elfogadva | 2/2 | 4ms | 5392 KiB | |||
21 | Elfogadva | 2/2 | 4ms | 4720 KiB | |||
22 | Elfogadva | 2/2 | 4ms | 5580 KiB |