2 条题解
-
0
把每个车站看作一个点,将这个车站相连的第一个边设为0,其余为1. 跑一边最短路,累加即可。
#include <bits/stdc++.h> using namespace std; int n, m, k, A, B, d[105][105]; int main() { memset (d, 0x3f, sizeof(d)); cin >> n >> A >> B; for (int i = 0; i <= n; i++) d[i][i] = 0; for (int i = 1; i <= n; i++) { cin >> k; for (int j = 1; j <= k; j++) { cin >> m; if (j == 1) d[i][m] = 0; else d[i][m] = 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]); if (d[A][B] == 0x3f3f3f3f) cout << -1; else cout << d[A][B]; return 0; }
-
0
把每个车站看作一个点,将这个车站相连的第一个边设为0,其余为1. 跑一边最短路,累加即可。
#include <bits/stdc++.h> using namespace std; int n, m, k, A, B, d[105][105]; int main() { memset (d, 0x3f, sizeof(d)); cin >> n >> A >> B; for (int i = 0; i <= n; i++) d[i][i] = 0; for (int i = 1; i <= n; i++) { cin >> k; for (int j = 1; j <= k; j++) { cin >> m; if (j == 1) d[i][m] = 0; else d[i][m] = 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]); if (d[A][B] == 0x3f3f3f3f) cout << -1; else cout << d[A][B]; return 0; }
- 1
信息
- ID
- 5404
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 3
- 标签
- 递交数
- 11
- 已通过
- 3
- 上传者