题意:有n个路口,每个路口通向其他某些路口,但是每个路口的轨道有方向,初始时指向第一个给出的路口的方向,如果要去其他路口,就需要下车操作一次路口转换器,让轨道改向需要的方向,问A路口到B路口需要操作转换器的最少次数。
对于每个路口,第一个指向路口的边权值为 0 表示花费 0 次操作,其余边权值为 1 表示花费 1 次操作。直接求最短路就行。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<stdio.h>
2 #include<string.h>
3 #include<vector>
4 #include<queue>
5 #include<algorithm>
6 using namespace std;
7 typedef pair<int,int> pii;
8
9 struct cmp{
10 bool operator()(pii a,pii b){
11 return a.first>b.first;
12 }
13 };
14
15 int head[105],point[10005],next[10005],val[10005],size;
16 int n,s,t,dist[105];
17
18 void add(int a,int b,int v){
19 point[size]=b;
20 val[size]=v;
21 next[size]=head[a];
22 head[a]=size++;
23 }
24
25 void dij(){
26 int i;
27 memset(dist,-1,sizeof(dist));
28 dist[s]=0;
29 priority_queue<pii,vector<pii>,cmp>q;
30 q.push(make_pair(dist[s],s));
31 while(!q.empty()){
32 pii u=q.top();
33 q.pop();
34 if(u.first>dist[u.second])continue;
35 for(i=head[u.second];~i;i=next[i]){
36 int j=point[i],v=u.first+val[i];
37 if(dist[j]==-1||dist[j]>v){
38 dist[j]=v;
39 q.push(make_pair(dist[j],j));
40 }
41 }
42 }
43 printf("%d
",dist[t]);
44 }
45
46 int main(){
47 while(scanf("%d%d%d",&n,&s,&t)!=EOF){
48 int i,j;
49 memset(head,-1,sizeof(head));
50 size=0;
51 for(i=1;i<=n;i++){
52 int num;
53 scanf("%d",&num);
54 for(j=1;j<=num;j++){
55 int b;
56 scanf("%d",&b);
57 add(i,b,j==1?0:1);
58 }
59 }
60 dij();
61 }
62 return 0;
63 }