题解 P1346 【电车】

· · 题解

这道题的关键在建图

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

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

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

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

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

但是还有一个小细节；

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

附ac代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100+10;
const int inf=1e+8;
int g[maxn][maxn];
int n,m,k,f,t;
int main()
{
    scanf("%d%d%d",&n,&f,&t);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {g[i][j]=inf;g[i][i]=0;} 
    for(int i=1;i<=n;i++){
    scanf("%d",&k);
    for(int j=1;j<=k;j++){
    int a;
    scanf("%d",&a);
    if(j==1)g[i][a]=0;
    else g[i][a]=1;
    }
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    if(g[f][t]==inf)puts("-1");
    else printf("%d",g[f][t]);
}
//类似这种转化的还可以看看 洛谷上奇怪的电梯，思路差不多相同但是要用spfa；
//希望对你们有帮助，rp++