题目链接

题目大意

有一个火车站，里面有n条轨道，然后有n个轨道切换点。问最多切换几次，能从A轨道切换到B轨道。 每个轨道切换点能切换至m条轨道上，其中第一条可以切换的轨道不算切换次数，因为本来就是往那条轨道上运行过去。 如果不能从A轨道切换到B轨道，则输出-1。

思路分析

这道题算是比较裸的dijkstra算法，当然还有其他算法。问题的关键是如何建边，其实很简单，这道题的边的权值只有1和0两种情况，0是切换点后面的第一条轨道，1是切换点后面剩下的其他轨道。这样建好边后就可以直接用很裸的dijkstra算法做了。

//168K 0MS #define inf 0x3f3f3f3f #define ll long long #define vec vector<int> #define P pair<int,int> #define MAX 105 struct edge { int v, d; edge(int a = 0, int b = 0) { v = a, d = b; } }; int N, A, B, K, n, dis[MAX]; vector<edge> G[MAX]; int dijstra() { fill(dis, dis + MAX, inf);dis[A] = 0; priority_queue<P, vector<P>, greater<P> > q; q.push(P(0, A)); while (!q.empty()) { int u = q.top().second, d = q.top().first; q.pop(); if (d > dis[u])continue; if (u == B)return dis[u]; for (int i = 0; i < G[u].size(); i++) { edge e = G[u][i]; if (dis[e.v] > dis[u] + e.d) { dis[e.v] = dis[u] + e.d; q.push(P(dis[e.v], e.v)); } } } return -1; } int main() { while (scanf("%d %d %d", &N, &A, &B) != EOF) { for (int i = 0; i <= N; i++)G[i].clear(); for (int i = 1; i <= N; i++) { scanf("%d", &K); scanf("%d", &n); G[i].push_back(edge(n, 0));//初始这个方向不需要转换 for (int j = 1; j < K; j++) scanf("%d", &n), G[i].push_back(edge(n, 1));//其余的路口需要人工转换 } cout << dijstra() << endl; } }