9173 | 2024. 02. 16 19:30:39 | mraron | A lehető legkevesebb metróval utazás (40 pont) | cpp17 | Futási hiba 30/40 | 273ms | 64156 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, start, end;
cin >> n >> m >> start >> end;
vector<vector<int>> metro(n);
vector<vector<int>> adj(m + 1);
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
metro[i].resize(a);
for (int j = 0; j < a; j++)
{
int b;
cin >> b;
adj[b].push_back(i);
metro[i].push_back(b);
}
}
priority_queue<array<int, 4>, vector<array<int, 4>>, greater<array<int, 4>>> q;
q.push({0, start, -2, -2});
vector<int> dist(m + 1, INF);
vector<pair<int, int>> parent(m + 1);
while (!q.empty())
{
auto [d, v, p, met] = q.top();
q.pop();
if (dist[v] != INF)
{
continue;
}
dist[v] = d;
parent[v] = {p, met};
for (int i : adj[v])
{
for (int j : metro[i])
{
if (dist[j] > dist[v] + 1)
{
array<int, 4> pb;
pb[0] = dist[v] + 1;
pb[1] = j;
pb[2] = v;
pb[3] = i;
q.push(pb);
}
}
}
}
if (dist[end] == INF)
{
cout << "-1";
return 0;
}
cout << dist[end] << "\n";
vector<int> ans;
while (true)
{
if(parent[end].second==-2) break;
ans.push_back(parent[end].second);
end = parent[end].first;
}
reverse(ans.begin(), ans.end());
for (int i : ans)
cout << i + 1 << " ";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 30/40 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1752 KiB | |||
2 | Elfogadva | 0/0 | 93ms | 4788 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2068 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2116 KiB | |||
5 | Elfogadva | 2/2 | 4ms | 2912 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2468 KiB | |||
7 | Elfogadva | 2/2 | 144ms | 7088 KiB | |||
8 | Elfogadva | 2/2 | 240ms | 36264 KiB | |||
9 | Futási hiba | 0/2 | 70ms | 64156 KiB | |||
10 | Elfogadva | 2/2 | 273ms | 36656 KiB | |||
11 | Elfogadva | 2/2 | 28ms | 7684 KiB | |||
12 | Elfogadva | 2/2 | 125ms | 7048 KiB | |||
13 | Elfogadva | 2/2 | 127ms | 7024 KiB | |||
14 | Elfogadva | 2/2 | 104ms | 7204 KiB | |||
15 | Futási hiba | 0/2 | 175ms | 63432 KiB | |||
16 | Futási hiba | 0/2 | 175ms | 63456 KiB | |||
17 | Futási hiba | 0/2 | 174ms | 63428 KiB | |||
18 | Futási hiba | 0/2 | 175ms | 63336 KiB | |||
19 | Elfogadva | 2/2 | 41ms | 5052 KiB | |||
20 | Elfogadva | 2/2 | 78ms | 6068 KiB | |||
21 | Elfogadva | 2/2 | 16ms | 4676 KiB | |||
22 | Elfogadva | 2/2 | 92ms | 6480 KiB |