AcWing 4249. Floyd 板子
原题链接
简单
作者:
cyzh
,
2022-03-01 01:35:58
,
所有人可见
,
阅读 385
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {
int n, A, B; cin >> n >> A >> B;
// 把d数组初始化为邻接矩阵
vector<vector<int>> d(n + 1, vector<int>(n + 1, 1e9));
// for (int i = 1; i <= n; i++) d[i][i] = 0;
for(int i = 1; i <= n; i++){
int x, y; cin >> x;
for(int j = 0; j < x; j++) cin >> y, d[i][y] = !!j;//如果是第一个点,!!j = 0,其他点!!j = 1
}
// floyd求任意两点间最短路径
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]);
// 输出
cout << (d[A][B] == 1e9 ? -1 : d[A][B]);
}