P1346 电车

题目描述

在一个神奇的小镇上有着一个特别的电车网络，它由一些路口和轨道组成，每个路口都连接着若干个轨道，每个轨道都通向一个路口（不排除有的观光轨道转一圈后返回路口的可能）。在每个路口，都有一个开关决定着出去的轨道，每个开关都有一个默认的状态，每辆电车行驶到路口之后，只能从开关所指向的轨道出去，如果电车司机想走另一个轨道，他就必须下车切换开关的状态。

为了行驶向目标地点，电车司机不得不经常下车来切换开关，于是，他们想请你写一个程序，计算一辆从路口A到路口B最少需要下车切换几次开关。

输入输出格式

输入格式：

第一行有3个整数2<=N<=100，1<=A，B<=N，分别表示路口的数量，和电车的起点，终点。

接下来有N行，每行的开头有一个数字Ki(0<=Ki<=N-1)，表示这个路口与Ki条轨道相连，接下来有Ki个数字表示每条轨道所通向的路口，开关默认指向第一个数字表示的轨道。

输出格式：

输出文件只有一个数字，表示从A到B所需的最少的切换开关次数，若无法从A前往B，输出-1。

输入输出样例

输入样例#1：

输出样例#1：

题解

建图时默认路径边的长度为0 其他为1，即可

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<cstring>
 5 using namespace std;
 6 struct node{
 7     int pos,l;
 8     friend bool operator <(node x,node y)
 9     {
10         return x.l >y.l ;
11     }
12 
13 };
14 priority_queue<node>s;
15 int mapp[105][105],vis[105] ;
16 int n,ss,t;
17 const int INF=0x3f3f3f3f;
18 void dijkstra(int end)
19 {
20     node temp,x;
21     temp.l =0;
22     temp.pos =ss;
23     s.push(temp);
24     int flag=0;
25     while(!s.empty())
26     {
27         temp=s.top();
28         x=temp;
29         s.pop();
30         int stra=temp.pos ;
31         if(stra==end)
32         {
33             flag=1;
34             break;
35         }
36 
37 
38         vis[stra]=1;
39         for(int i=1;i<=n;i++)
40         {
41             if(!vis[i]&&mapp[stra][i]<INF)
42             {
43                 temp.pos =i;
44                 temp.l +=mapp[stra][i];
45                 s.push(temp);
46             }
47             temp=x;
48         }
49     }
50     if(!flag) printf("-1
");
51     else
52     printf("%d
",temp.l );
53 }
54 
55 int main()
56 {
57         scanf("%d%d%d",&n,&ss,&t);
58         memset(vis,0,sizeof(vis));
59         memset(mapp,0x3f,sizeof(mapp));
60         int num,k;
61         for(int i=1;i<=n;i++)
62         {
63             scanf("%d",&num);
64             for (int j = 1; j <=num ; ++j) {
65                 scanf("%d",&k);
66                 if(j==1) mapp[i][k]=0;
67                 else mapp[i][k]=1;
68             }
69         }
70         dijkstra(t);
71         while(!s.empty())
72             s.pop();
73 
74     return 0;
75 }