首页 > > 程序设计 > C/C++ >

洛谷 P1346 电车

2018-09-05 07:42:36来源：博客园阅读 ()

这道题的关键在建图

把每一个车站看成一个点，将这个车站相连的第一个车站建立一条边权为0的边，对于它所相连的其他车站，建立边权为1的边；

这样我们可以得到一张图；

起点，终点都知道了，跑一边最短路即可

最短路可以用spfa，floyd，迪杰斯特拉；

因为n只有200，跑遍floyd就行；

但是还有一个小细节；

对于我们建的每一条边，都只是单向边，不要加上f【i】【j】=f【j】【i】；

附ac代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<string>
 6 #include<queue>
 7 #include<cmath> 
 8 #include<ctime>
 9 const int MAXN=100+5;
10 const int INF=0x3f3f3f;
11 int dis[MAXN][MAXN];
12 int main()
13 {
14     int n,a,b;
15     int c,d;
16     scanf("%d %d %d",&n,&a,&b);
17     for(int i=1;i<=MAXN-2;i++)
18         for(int j=1;j<=MAXN-2;j++)
19             dis[i][j]=INF;
20     for(int i=1;i<=n;i++)
21     {
22         scanf("%d",&c);
23         for(int j=1;j<=c;j++)
24         {
25             scanf("%d",&d);
26             j==1?dis[i][d]=0:dis[i][d]=1;
27         }
28     }
29 
30     for(int k=1;k<=n;k++)
31         for(int i=1;i<=n;i++)
32             for(int j=1;j<=n;j++)
33                 dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]); 
34     dis[a][b]==INF?printf("-1"):printf("%d",dis[a][b]); 
35 
36     return 0;
37 
38 }