洛谷 P8893. 「UOI-R1」智能推荐
原题链接
简单
作者:
y总的小迷弟
,
2023-08-01 20:28:59
,
所有人可见
,
阅读 118
#include<bits/stdc++.h>
using namespace std;
int n, k, p, r, ans = -1;
bool flag = false;
int h[5010], e[25000010], ne[25000010], idx = 0, id[5010];
int deg[5010];
struct xyh
{
int ver;
int date;
int cnt;
};
queue<xyh> q;
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx++;
}
void topsort()
{
int num = 0;
for(int i = 0;i < p;i++)
{
num++;
q.push({id[i], 0, num});
}
while(!q.empty())
{
auto t = q.front();
q.pop();
int ver = t.ver, date = t.date, cnt = t.cnt;
if(ver == k)
{
ans = date;
flag = true;
return;
}
for(int i = h[ver];i != -1;i = ne[i])
{
int j = e[i];
deg[j]--;
if(deg[j] == 0)
{
cnt++;
q.push({j, date + 1, cnt});
}
}
}
}
int main()
{
memset(h, -1, sizeof(h));
cin >> n >> k >> p;
for(int i = 0;i < p;i++)
cin >> id[i];
cin >> r;
while(r--)
{
int v, s;
cin >> v >> s;
while(s--)
{
int x;
cin >> x;
add(x, v);
deg[v]++;
}
}
topsort();
cout << ans << endl;
return 0;
}