AcWing 1562. 微博转发-Floyd版
原题链接
中等
作者:
郭松源
,
2021-02-09 22:17:27
,
所有人可见
,
阅读 1431
Floyd最短路, PAT不开氧气优化能过
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int d[N][N];
int n, m, p;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
for (int i = 1; i <= n; i ++ )
{
int s;
scanf("%d", &s);
for (int j = 0; j < s; j ++ )
{
int x;
scanf("%d", &x);
d[x][i] = 1;
}
}
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
scanf("%d", &p);
while (p -- )
{
int x;
scanf("%d", &x);
int cnt = 0;
for (int i = 1; i <= n; i ++ )
if (i != x && d[x][i] <= m) cnt ++ ;
printf("%d\n", cnt);
}
return 0;
}
woc,你这真能过,为什么我的不行大佬,
你这个能过嘛,我自己写了个Floyd,可是时间超限了,
大佬,dijkstra怎么过呢,题目理解清楚了,但是dijkstra只是求单源最短路的,如果要求层数,该怎么想呢
用01bfs时间复杂度O(n^3/64)可以完美通过