洛谷 P1346 电车

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

新老客户大回馈,云服务器低至5折

这道题的关键在建图

把每一个车站看成一个点,将这个车站相连的第一个车站建立一条边权为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 }

更多代码请进入:https://github.com/tomatoschool

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:NYOJ1238 最小换乘 (dijkstra)

下一篇:ZR#317.【18 提高 2】A(计算几何 二分)