Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 10622 | Accepted: 3877 |
Description
it can leave only in the direction the switch is pointing. If the driver wants to go some other way, he/she has to manually change the switch.
When a driver has do drive from intersection A to the intersection B he/she tries to choose the route that will minimize the number of times he/she will have to change the switches manually.
Write a program that will calculate the minimal number of switch changes necessary to travel from intersection A to intersection B.
Input
Each of the following N lines contain a sequence of integers separated by a single blank character. First number in the i-th line, Ki (0 <= Ki <= N-1), represents the number of rails going out of the i-th intersection. Next Ki numbers represents the intersections
directly connected to the i-th intersection.Switch in the i-th intersection is initially pointing in the direction of the first intersection listed.
Output
Sample Input
3 2 1 2 2 3 2 3 1 2 1 2
Sample Output
0
Source
最短路上不会有环,所以每个点顶多走过一次,那么就不需要去考虑走过这个点以后,开关的位置,所以直接按起始时开关位置建图,然后floyd就行
/************************************************************************* > File Name: poj1847.cpp > Author: ALex > Mail: zchao1995@gmail.com > Created Time: 2015年02月05日 星期四 14时37分08秒 ************************************************************************/ #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const double pi = acos(-1); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair <int, int> PLL; const int N = 110; int dp[N][N]; int main () { int n, a, b; while (~scanf("%d%d%d", &n, &a, &b)) { memset (dp, inf, sizeof(dp)); int k, j; for (int i = 1; i <= n; ++i) { scanf("%d", &k); if (k == 0) { continue; } k--; scanf("%d", &j); dp[i][j] = 0; while (k--) { scanf("%d", &j); dp[i][j] = 1; } } for (int i = 1; i <= n; ++i) { dp[i][i] = 0; } for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dp[i][j] = min (dp[i][k] + dp[k][j], dp[i][j]); } } } if (dp[a][b] != inf) { printf("%d\n", dp[a][b]); } else { printf("-1\n"); } } return 0; }