基本上是裸的最短路,是第一个不用扳道岔的边长就是0,后面的需要扳道岔的长度就是1。然后愉快的套一个Dijkstra板子就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include<iostream> #include<vector> #include<queue> #include<cstring> using namespace std; int n,a,b; struct edge{ int v,w; edge(int vv,int ww){v=vv;w=ww;} bool operator < (const edge& e2) const{ return w>e2.w; } }; vector<edge> edges[105]; priority_queue<edge> pq; bool visited[105]; int dis[105]; int main(){ ios::sync_with_stdio(false); cin>>n>>a>>b; for(int i=1;i<=n;i++){ int t; cin>>t; for(int j=1;j<=t;j++){ int v; cin>>v; if(j==1)edges[i].push_back(edge(v,0)); else edges[i].push_back(edge(v,1)); } } //Dijkstra memset(dis,0x7f,sizeof(dis)); pq.push(edge(a,0)); while(!pq.empty()){ edge cur=pq.top(); pq.pop(); if(visited[cur.v])continue; visited[cur.v]=true; dis[cur.v]=cur.w; for(int i=0;i<edges[cur.v].size();i++){ if(!visited[edges[cur.v][i].v]&&dis[edges[cur.v][i].v]>dis[cur.v]+edges[cur.v][i].w){ dis[edges[cur.v][i].v]=dis[cur.v]+edges[cur.v][i].w; pq.push(edge(edges[cur.v][i].v,dis[edges[cur.v][i].v])); } } } if(dis[b]!=0x7f7f7f7f)cout<<dis[b]; else cout<<-1; } |