题意:有向图有N个点,当电车进入交叉口(某点)时,它只能在开关指向的方向离开。 如果驾驶员想要采取其他方式,他/她必须手动更换开关。当驾驶员从路口A驶向路口B时,他/她尝试选择将他/她不得不手动更换开关的次数最小化的路线。
编写一个程序,该程序将计算从交点A到交点B所需的最小开关更改次数。第i个交点处的开关最初指向列出的第一个交点的方向。
分析:对于某点i,去往其直接可到达的点列表中的第一个点时不需要更换开关,等价于边长为0;而其他的点需要更换开关,等价于边长为1。dijkstra裸题。
#include<cstdio> #include<map> #include<iostream> #include<cstring> #include<queue> using namespace std; const int MAXN = 100 + 10; const int INF = 0x3f3f3f3f; struct Edge{ int from, to, dist; Edge(int f, int t, int d):from(f), to(t), dist(d){} }; struct HeapNode{ int d, u; HeapNode(int dd, int uu):d(dd), u(uu){} bool operator < (const HeapNode&rhs)const{ return d > rhs.d; } }; struct Dijkstra{ int n, m; vector<int> G[MAXN]; vector<Edge> edges; bool done[MAXN]; int d[MAXN]; int p[MAXN]; void init(int n){ this -> n = n; for(int i = 1; i <= n; ++i) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int dist){ edges.push_back(Edge(from, to, dist)); m = edges.size(); G[from].push_back(m - 1); } void dijkstra(int s){ priority_queue<HeapNode> q; for(int i = 1; i <= n; ++i) d[i] = INF; memset(done, false, sizeof done); d[s] = 0; q.push(HeapNode(0, s)); while(!q.empty()){ HeapNode top = q.top(); q.pop(); if(done[top.u]) continue; done[top.u] = true; int len = G[top.u].size(); for(int i = 0; i < len; ++i){ Edge e = edges[G[top.u][i]]; if(d[top.u] + e.dist < d[e.to]){ d[e.to] = d[top.u] + e.dist; p[e.to] = G[top.u][i]; q.push(HeapNode(d[e.to], e.to)); } } } } }dij; int main(){ int N, A, B; scanf("%d%d%d", &N, &A, &B); dij.init(N); for(int i = 1; i <= N; ++i){ int k, x; scanf("%d", &k); for(int j = 0; j < k; ++j){ scanf("%d", &x); if(j == 0) dij.AddEdge(i, x, 0); else dij.AddEdge(i, x, 1); } } dij.dijkstra(A); if(dij.d[B] == INF) printf("-1 "); else printf("%d ", dij.d[B]); return 0; }